这个是一个哈希+线段树,这个题目也不算特别难,但是呢,还比较有意思。
这个题目给你两个操作,一个是回答l~r 区间是不是回文,一个是对一个点进行单点修改。
这个用哈希还是比较好用的,首先就是把所有字符映射成一个数字,然后就相当于给你一串数字进行以上操作。
这个最好就是从小到达进行一个递增的哈希,这个看代码吧,说不太清楚。
主要注意一点就是最后要保证这个哈希的位数是一样的,具体看代码。
#include<cstdio> #include<iostream> #include<algorithm> #include<string> #include<cstring> #include<vector> #include<queue> #include<stack> #include<map> #include<set> #include<cmath> #include<sstream> #define inf 0x3f3f3f3f using namespace std; typedef long long ll; typedef unsigned long long ull; const int maxn = 1e5 + 10; const ull base = 13331; ull h[maxn], p[maxn]; ull sum1[maxn * 8], sum2[maxn * 8]; int n, m; char str1[maxn], str2[maxn]; void push_up(int id) { sum1[id] = sum1[id << 1] + sum1[id << 1 | 1]; sum2[id] = sum2[id << 1] + sum2[id << 1 | 1]; //printf("sum[%d]=%llu nisum[%d]=%llu\n", id, sum[id], id, nisum[id]); } void build(int id, int l, int r) { if (l == r) { sum1[id] = (str1[l] - 'a' + 1)*p[l];//哈希赋值,从小往大,递增赋值 sum2[id] = (str2[l] - 'a' + 1)*p[l]; return; } int mid = (l + r) >> 1; build(id << 1, l, mid); build(id << 1 | 1, mid + 1, r); push_up(id); } void update(int id, int l, int r, int pos, int val, int f) { if (l == r) { if (f == 1) sum1[id] = val * p[l]; else sum2[id] = val * p[l]; return; } int mid = (l + r) >> 1; if (pos <= mid) update(id << 1, l, mid, pos, val, f); else update(id << 1 | 1, mid + 1, r, pos, val, f); push_up(id); } ull query(int id, int l, int r, int x, int y, int f) { if (x <= l && y >= r) { if (f == 1) return sum1[id]; return sum2[id]; } int mid = (l + r) >> 1; ull ans = 0; if (x <= mid) ans += query(id << 1, l, mid, x, y, f); if (y > mid) ans += query(id << 1 | 1, mid + 1, r, x, y, f); return ans; } char s[maxn], ch[10]; int main() { scanf("%s", str1 + 1); n = strlen(str1 + 1); p[0] = 1; for (int i = 1; i <= n; i++) p[i] = p[i - 1] * base, str2[i] = str1[n + 1 - i]; build(1, 1, n); scanf("%d", &m); while (m--) { int x, y; scanf("%s", s); if (s[0] == 'p') { scanf("%d%d", &x, &y); ull rest1 = query(1, 1, n, x, y, 1);//这样子查询还是有点难想的 ull rest2 = query(1, 1, n, n + 1 - y, n + 1 - x, 2); if (x < n + 1 - y) rest1 *= p[n + 1 - x - y];//这个if是保证这两个rest的数量级是一样的,这个可以画一个x轴就知道了 else rest2 *= p[x + y - n - 1]; if (rest1 == rest2) printf("Yes\n"); else printf("No\n"); } else { scanf("%d%s", &x, ch); update(1, 1, n, x, ch[0] - 'a' + 1, 1); update(1, 1, n, n - x + 1, ch[0] - 'a' + 1, 2); } } }
本站转载的文章为个人学习借鉴使用,本站对版权不负任何法律责任。如果侵犯了您的隐私权益,请联系我们删除。