E – Adnan and the Burned drivers题目：
给出一个长度为1e5的字符串，有1e5次操作。
操作1：修改一个字符串里的某个字符。操作2：询问字符串的\([l, r]\)是否为回文子串。
思路：
对于一个字符串快速判断是否为回文串，可以用字符串哈希通过判断正反哈希值是否相等，在\(O(logn)\)的时间内解决该问题。但是本题有一个问题是带修，那么我们可以考虑用数据结构来维护这个带修的过程。查询哈希值的过程就可以看做是一个区间求和问题，修改字符就是单点修改问题。要注意的是，要维护一个正方向的哈希值和一个反方向的哈希值。
实现：
关于字符串哈希，用unsigned long long可以自动取模，基准数可以是131或者27。
在线段树维护区间和的时候，需要注意左移和右移。
#include using namespace std;const int N = 100005;typedef unsigned long long ull;char str[N];ull bash[N * 4];int n, m;ull seg1[N * 4], seg2[N * 4];void pushup(int k, int l, int r){ int mid = l + r >> 1; seg1[k] = (seg1[k << 1] * bash[r - mid] + seg1[k << 1 | 1]); seg2[k] = (seg2[k << 1] + seg2[k <> 1; if(x <= mid) update(k << 1, l, mid, x, val); else update(k <> 1; if(qr <= mid) return query(k << 1, l, mid, ql, qr, q); else if(mid < ql) return query(k << 1 | 1, mid + 1, r, ql, qr, q); else if(q == 1) return query(k << 1, l, mid, ql, mid, q) * bash[qr - mid] + query(k << 1 | 1, mid + 1, r, mid + 1, qr, q); else return query(k << 1, l, mid, ql, mid, q) + bash[mid - ql + 1] * query(k << 1 | 1, mid + 1, r, mid + 1, qr, q);}void init(){ bash[0] = 1; for(int i = 1; i <= 4e5; i ++) bash[i] = bash[i - 1] * 131;}void solve(){ memset(seg1, 0, sizeof seg1); memset(seg2, 0, sizeof seg2); scanf("%d%d", &n, &m); scanf("%s", str + 1); for(int i = 1; i > 1; ull q, p; if((y - x + 1) & 1) //区间长度为奇数 q = query(1, 1, n, x, mid - 1, 0), p = query(1, 1, n, mid + 1, y, 1); else //偶数 q = query(1, 1, n, x, mid, 0), p = query(1, 1, n, mid + 1, y, 1); if(q == p) puts("Adnan Wins"); else puts("ARCNCD!"); } } }}int main(){ init(); int _; scanf("%d", &_); while(_--) solve();}