题意：给一个字符串s，两个操作，一个是询问s[l..r]是否回文，另一个是把s[i]的字符变成c
思路：判断回文可以做正反两个哈希，容易想到修改可以用树状数组维护，不过多项式就要反过来
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #include<iostream> 5 #define LL long long 6 #define uLL unsigned long long 7 #define debug(x) cout << "[" << x << "]" << endl 8 using namespace std; 9 10 const int mx = 1e5+10; 11 const int base = 27; 12 uLL bit[mx][2], p[mx]; 13 char s[mx]; 14 int n; 15 16 void upd(int x, int y, uLL c){ 17 while (x <= n){ 18 bit[x][y] += c; 19 x += x&-x; 20 } 21 } 22 23 uLL sum(int x, int y){ 24 uLL ans = 0; 25 while (x){ 26 ans += bit[x][y]; 27 x -= x&-x; 28 } 29 return ans; 30 } 31 32 int main(){ 33 int q; 34 p[0] = 1; 35 for (int i = 1; i < mx; i++) p[i] = p[i-1]*base; 36 while (scanf("%s", s) == 1){ 37 n = strlen(s); 38 memset(bit, 0, sizeof bit); 39 for (int i = 0; i < n; i++){ 40 upd(i+1, 0, p[i]*(s[i]-'a')); 41 upd(i+1, 1, p[i]*(s[n-i-1]-'a')); 42 } 43 scanf("%d", &q); 44 char op[20]; 45 while (q--){ 46 int x, y; 47 char c[2]; 48 scanf("%s%d", op, &x); 49 if (op[0] == 'p'){ 50 scanf("%d", &y); 51 uLL l = p[n-y]*(sum(y, 0)-sum(x-1, 0)); 52 uLL r = p[x-1]*(sum(n-x+1, 1)-sum(n-y, 1)); 53 printf("%s ", (l == r) ? "Yes" : "No"); 54 } 55 else { 56 scanf("%s", c); 57 upd(x, 0, (c[0]-s[x-1])*p[x-1]); 58 upd(n-x+1, 1, (c[0]-s[x-1])*p[n-x]); 59 s[x-1] = c[0]; 60 } 61 } 62 } 63 return 0; 64 }