URAL - 1989 Subpalindromes——字符串哈希 + 线段树

URAL - 1989 Subpalindromes——字符串哈希 + 线段树

题意：判断是否为回文串

思路：两颗线段树存一段字符串的正向哈希值和反向哈希值，具体思路看别的博客吧，我query函数忘记改ull错了13遍已经没脸见人了。。。

#include #include #include #include using namespace std;typedef unsigned long long ull;const int maxn = 1e5 + 10;const int k = 123;char str[maxn], op[100];int n;ull p[maxn], date[maxn], segTree[2][maxn<<2];void pushup(int root, int flag) { segTree[flag][root] = segTree[flag][root<<1] + segTree[flag][root<<1|1];}void build(int L, int R, int root, int flag) { if (L == R) { segTree[flag][root] = date[L]; return; } int mid = (L + R)>>1; build(L, mid, root<<1, flag); build(mid + 1, R, root<<1|1, flag); pushup(root, flag);}void update_node(int L, int R, int root, int pos, ull val, int flag) { if (L == R) { segTree[flag][root] = val; return; } int mid = (L + R)>>1; if (pos <= mid) { update_node(L, mid, root<<1, pos, val, flag); } else { update_node(mid + 1, R, root<<1|1, pos, val, flag); } pushup(root, flag);}ull query(int L, int R, int root, int qL, int qR, int flag) { if (qL <= L && R <= qR) { return segTree[flag][root]; } int mid = (L + R)>>1; ull temp = 0; if (qL <= mid) { temp += query(L, mid, root<<1, qL, qR, flag); } if (qR > mid) { temp += query(mid + 1, R, root<<1|1, qL, qR, flag); } return temp;}int main(){ while (scanf("%s", str) != EOF) { n = strlen(str); for (int i = 0; i <= n * 4; i++) { segTree[0][i] = segTree[1][i] = 0; } p[0] = 1; for (int i = 1; i <= n; i++) { p[i] = p[i - 1] * k; } for (int i = 0; i < n; i++) { date[i + 1] = p[i] * (ull)str[i]; } build(1, n, 1, 0); reverse(str, str + n); for (int i = 0; i < n; i++) { date[i + 1] = p[i] * (ull)str[i]; } build(1, n, 1, 1); int q; scanf("%d", &q); while (q--) { scanf("%s", op); if (op[0] == 'p') { int a, b; scanf("%d %d", &a, &b); if (a > b) { int t = a; a = b; b = t; } ull temp1 = query(1, n, 1, a, b, 0); ull temp2 = query(1, n, 1, n - b + 1, n - a + 1, 1); int t1 = a - 1, t2 = n - b; if (t1 < t2) temp1 *= p[t2 - t1]; else temp2 *= p[t1 - t2]; if (temp1 == temp2) { printf("Yes\n"); } else { printf("No\n"); } } else { int a; char b; scanf("%d %c", &a, &b); update_node(1, n, 1, a, p[a - 1] * (ull)b, 0); update_node(1, n, 1, n - a + 1, p[n - a] * (ull)b, 1); } } } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。