题意:给一个字符串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\n", (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 }
转载于:https://www.cnblogs.com/QAQorz/p/9733852.html