Gym 100570E : Palindrome Query

De Prezer loves palindrome strings. A string s ₁ s ₂ ... s _n is palindrome if and only if it is equal to its reverse.

De Prezer also loves queries.

You are given string s of length  n  and  m  queries. There are 3 types of queries :

1. 1 p x  : Modify  s _p = x  where  1 ≤ p ≤ n  and  x  is a lower case English letter.

2. 2 p  : Print the length of the largest palindrome substring of  s  like  s _l s _{l + 1} ... s _r  such that  l ≤ p ≤ r  and  r - p = p - l . ( 1 ≤ p ≤ n )

3. 3 p  : Print the length of the largest palindrome substring of  s  like  s _l s _{l + 1} ... s _r  such that  l ≤ p  and  p + 1 ≤ r  and  r - p - 1 = p - l . ( 1 ≤ p ≤ n - 1) or  - 1 if there is no such substring.

The first line of input contains s and  m .

Next m lines contain queries.

1 ≤ n , m ≤ 10 ⁵

s only contains lower case English letters.

For each query of type  2 and  3 print the answer in a single line.

解题报告：

大意就是给你一个字符串，有三种操作:

操作1：将某个位置的字符改成另外一个字符

操作2：询问以位置 x 位中点的奇回文串长度

操作3：询问以位置 x,x+1位中的偶回文串长度

我们建立一颗线段树来解决这个问题

线段树中的存储的 key1 表示 s[L] * p^0 +  S[L+1] * p ^1 + ..... S[R] * p ^ (R-L) , key2 值表示S[R] * p ^ 0 + S[R-1] * p ^1 + ...S[L] * p^(R-L)

显然key2 是倒着的，这样方便我们查询这个区间是否是回文子串

题目显然要求是单点更新，区间查询.

对于单点更新而言，最重要的就是push_up函数，我们考虑

将[L,mid] 和 [mid + 1 , R]进行合并时，注意到key值的含义，我们需要给右边的[mid+1,R]的key1值乘上p^(mid-L+1),key2则是给[L,mid]乘上(R-mid+1)

那么更新我们就解决了,查询呢

下面皆以 key1 为例(key2同理可得)

对于key1而言，我们主要就是要给落在右边的查询区间段上的乘上一个值.

假设我们现在要查询的区间段是[ ql , qr ] ,此时所在的线段是[L,R],中点是mid , 我们假设 qr > mid(即有落在右边的部分)

那么我们需要给右边乘的值就是p ^ (mid - ql + 1) <仔细想想>

key2同理可得，这里不再累述

这样我们就解决了查询问题，那么对于每个询问，我们二分答案即可

#include <iostream> #include <cstring> #include <cstdio> #include <algorithm> #include <cmath> #include <vector> #include <stack> #include <map> #include <set> #include <queue> #include <iomanip> #include <string> #include <ctime> typedef unsigned char byte; #define pb push_back #define input_fast std::ios::sync_with_stdio(false);std::cin.tie(0) #define local freopen("in.txt","r",stdin) #define pi acos(-1) using namespace std; typedef pair<unsigned int ,unsigned int> dl; const int maxn = 1e5 + 500; const unsigned int p1 = 131; const unsigned int p2 = 171; unsigned int value1[maxn]; unsigned int value2[maxn]; typedef struct treenode { int l , r ; dl key1,key2; void updata(unsigned int v) {  key1.first = key1.second = v;  key2.first = key2.second = v; } }; treenode tree[maxn * 4]; inline void build_tree(int o,int l,int r) { tree[o].l = l , tree[o].r = r , tree[o].key1.first = tree[o].key1.second = tree[o].key2.first = tree[o].key2.second = 0; if (r > l) { int mid = l + (r-l)/2; build_tree(2*o,l,mid); build_tree(2*o+1,mid+1,r); } } inline void push_up(int o) { int ac = tree[2*o].r - tree[2*o].l + 1 ; int ac2 = tree[2*o+1].r - tree[2*o+1].l + 1; tree[o].key1.first = tree[2*o].key1.first + tree[2*o+1].key1.first * value1[ac]; tree[o].key1.second = tree[2*o].key1.second + tree[2*o+1].key1.second * value2[ac]; tree[o].key2.first = tree[2*o].key2.first * value1[ac2] + tree[2*o+1].key2.first; tree[o].key2.second = tree[2*o].key2.second * value2[ac2] + tree[2*o+1].key2.second; } void updata(int ql,int qr,int o,unsigned int v) { int l = tree[o].l , r = tree[o].r; if (ql <= l && qr >= r) tree[o].updata(v); else { int mid = l + (r-l) / 2; if (mid >= ql) updata(ql,qr,2*o,v); if (mid < qr) updata(ql,qr,2*o+1,v); push_up(o); } } dl query(int ql,int qr,int o,int type) { int l = tree[o].l , r = tree[o].r; //cout << "L is " << l << " R is " << r << " ql is " << ql << " qr is " << qr << endl; if (ql == l && qr == r) {   if (type == 1) return tree[o].key1;   else return tree[o].key2; } else { int mid = l + (r-l) / 2 , ac; dl res(0,0) , temp; if (mid >= ql) {   int atr = min(mid,qr);   temp = query(ql,atr,2*o,type);   if (type == 2 && qr - mid > 0)    {    temp.first *= value1[qr - mid];    temp.second *= value2[qr - mid];    }    res.first += temp.first;    res.second += temp.second; } if (mid < qr) {   int ltr = max(ql,mid+1);   temp = query(ltr,qr,2*o+1,type);   if (type == 1 && mid - ql + 1 > 0)    {     temp.first *= value1[mid - ql + 1];     temp.second *= value2[mid - ql + 1];    }   res.first += temp.first;   res.second += temp.second; } //cout << "L is " << l << " R is " << r << " fist-value is " << res.first << " second-value is " << res.second << endl; return res; } } char str[maxn] , temp[200]; int length , m ; bool equaldl(dl x,dl y) {  return x.first == y.first && x.second == y.second; } int main(int argc,char *argv[]) {   scanf("%s%d",str,&m);   value1[0] = value2[0] = 1;   length = strlen(str);   build_tree(1,0,length-1);   for(int i = 1 ; i <= length ; ++ i)  {     value1[i] = value1[i-1]*p1;     value2[i] = value2[i-1]*p2;  }   for(int i = 0 ; i < length ; ++ i) updata(i,i,1,(unsigned int)str[i]);   while(m--)  {    int type,x;    scanf("%d",&type);    if (type == 1)     {       scanf("%d%s",&x,temp);       x--;       str[x] = temp[0];     updata(x,x,1,temp[0]);    }   else    {     scanf("%d",&x);     int L , R;     x--;     if (type == 2)      {       L = 1 , R = min(  x + 1 , length - x );       while(L < R)        {         int mid = L + (R-L+1) / 2;         int tl = x - mid + 1 ;        int tr = x + mid - 1 ;         if (equaldl(query(tl,tr,1,1),query(tl,tr,1,2))) L = mid;         else R = mid - 1;       }      printf("%d/n",2*L-1);     }    else     {      if (x+1 >= length || str[x] != str[x+1]) printf("-1/n");      else      {        int L = 1 , R  = min(x + 1 , length - x - 1);        while(L < R)         {         int mid = L + (R-L+1) / 2;         int tl = x - mid + 1;         int tr = x + mid;         if (equaldl(query(tl,tr,1,1),query(tl,tr,1,2))) L = mid;         else R = mid - 1;         }        printf("%d/n",2*L);       }     }    }  }   return 0; }