E. Palindrome Query
Time Limit: 20 Sec
Memory Limit: 256 MB
题目连接
http://codeforces.com/gym/100570/problem/E
Description
De Prezer loves palindrome strings. A string s1s2...sn 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 sp = 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 slsl + 1...sr 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 slsl + 1...sr 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.
Input
The first line of input contains s and m.
Next m lines contain queries.
1 ≤ n, m ≤ 105
s only contains lower case English letters.
Output
For each query of type 2 and 3 print the answer in a single line.
Sample Input
abcd 3
3 1
1 2 c
3 2
Sample Output
-1
2
HINT
题意
给你一个字符串，然后有3个操作
1.修改一个位置的字符为
2.查询以p为中心的奇数回文串最长长度
3.查询以p为中心的偶数回文串最长长度
题解：
这道题看起来很唬人，其实暴力可过……
直接傻逼暴力就好
我拍的是manacher，直接暴力修改，也是直接过了……
代码
//qscqesze
#include <cstdio>
#include <cmath>
#include <cstring>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
#include <sstream>
#include <queue>
#include <typeinfo>
#include <fstream>
#include <map>
#include <stack>
typedef long long ll;
using namespace std;
//freopen("D.in","r",stdin);
//freopen("D.out","w",stdout);
#define sspeed ios_base::sync_with_stdio(0);cin.tie(0)
#define test freopen("test.txt","r",stdin)
#define maxn 201001
#define mod 10007
#define eps 1e-9
int Num;
char CH[];
//const int inf=0x7fffffff; //нчоч╢С
const int inf=0x3f3f3f3f;
/* inline void P(int x)
{
Num=0;if(!x){putchar('0');puts("");return;}
while(x>0)CH[++Num]=x%10,x/=10;
while(Num)putchar(CH[Num--]+48);
puts("");
}
*/
inline ll read()
{
ll x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
inline void P(int x)
{
Num=;if(!x){putchar('');puts("");return;}
while(x>)CH[++Num]=x%,x/=;
while(Num)putchar(CH[Num--]+);
puts("");
}
//**************************************************************************************
char s[maxn];
char str[maxn];
int p[maxn];
int dp1[maxn];
int dp2[maxn];
int l;
void manacher(char s[],int l)
{
int i,j,k,ans=;
for(i=;i<=l;++i)str[i<<]=s[i],str[(i<<)+]='#';
str[]='#';str[l*+]='#';str[]='&';str[l*+]='$';
l=l*+;j=;
for(i=;i<=l;)
{
while(str[i-j-]==str[i+j+])++j;
p[i]=j;if(j>ans)ans=j;
for(k=;k<=j&&p[i]-k!=p[i-k];++k)p[i+k]=min(p[i-k],p[i]-k);
i+=k;j=max(j-k,);
}
}
struct node
{
int p;
char c;
};
vector<node> Q;
int main()
{
//test;
int m;
scanf("%s",s+);
scanf("%d",&m);
l=strlen(s+);
manacher(s,l);
l=l*+;
for(int ii=;ii<m;ii++)
{
int k;
scanf("%d",&k);
if(k==)
{
int pp;
pp=read();
char c;
scanf("%c",&c);
Q.push_back((node){pp,c});
}
if(k==)
{
if(Q.size())
{
for(int i=;i<Q.size();i++)
{
s[Q[i].p]=Q[i].c;
}
Q.clear();
manacher(s,l/);
}
int pp=read();
printf("%d\n",p[pp*]);
}
if(k==)
{
if(Q.size())
{
for(int i=;i<Q.size();i++)
{
s[Q[i].p]=Q[i].c;
}
Q.clear();
manacher(s,l/);
}
int pp=read();
if(p[pp*+]==)
printf("-1\n");
else
printf("%d\n",p[pp*+]);
}
}
}