题目大意
给出一个由N个整数组成的序列A,你需要应用M个操作:
I p x 在p 处插入一个元素 x (解释:这里插入是p - 1和p 之间插入) D p 删除p 处的一个元素 R p x 修改p 处元素的值为 x Q l r 查询一个区间[l,r]的最大子段和
N <= 100000, M <= 100000
主要思路:FHQ Treap 维护区间
同学们应该都做过GSS系列其他的一些题目,所以维护最大子段和的具体套路这里就不详讲了。真的不懂的话看这里的后半篇
我的代码中套用了与楼下GKxx大佬的update方式,也就是习惯性的分情况讨论。
然后就是FHQ Treap维护区间的问题了。(这里默认大家会FHQ Treap的维护数据的写法,如果是Splay党的话,推荐GKxx大佬的题解)
我们在维护数据时,split是按照值的大小来分的:
inline void split(int rt, int k, int &x, int &y) { if(!rt) x = y = 0; else { if(k > z[rt].w) { y = rt, split(z[rt].ch[0], k, x, z[rt].ch[0]); } else { x = rt, split(z[rt].ch[1], k, z[rt].ch[1], y); } update(rt); } }
但是对于一个区间,我们总不能在哪个位置就把另外设的一个权值标上位置吧,这样插入时会有一定的错误。
这时我们可以采用类似findkth的方法split,也就是按照这个点的size值来找第几个。如:
inline void split(int rt, int k, int &x, int &y) { if(!rt) x = y = 0; else { if(k <= z[z[rt].ch[0]].sze) {// k与左儿子的size比较 y = rt, split(z[rt].ch[0], k, x, z[rt].ch[0]); } else { x = rt, split(z[rt].ch[1], k - z[z[rt].ch[0]].sze - 1, z[rt].ch[1], y); // 这里有个细节:右子树的size一定记得把k先减去左子树的size和这个节点(-1) } update(rt); } }
然后其他的就没有别的什么特别的了。在提取区间时只需要split一下r,然后split一下l - 1,分成的三棵子树中中间的那棵子树就是维护l ~ r的节点了。
记得开大点数组!!!否则WA的你天崩地裂(经验之谈)
(我开了大约400000才过,反正200000是过不了的,不太清楚为什么)
还有,记得开long long才行,因为数据范围(逃
code:
#include <iostream> #include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <algorithm> #include <queue> #include <map> #include <vector> #include <ctime> using namespace std; #define go(i, j, n, k) for(int i = j; i <= n; i += k) #define fo(i, j, n, k) for(int i = j; i >= n; i -= k) #define mn 400010 #define inf 1 << 30 #define ll long long inline int read() { int x = 0, f = 1; char ch = getchar(); while(ch > '9' || ch < '0') { if(ch == '-') f = -f; ch = getchar(); } while(ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); } return x * f; } struct tree{ int pri, ch[2], sze; ll x, sum, lsum, rsum, msum; } z[mn]; inline void update(int rt) { z[rt].sum = z[rt].x, z[rt].sze = 1; if (z[rt].ch[0]) z[rt].sum += z[z[rt].ch[0]].sum, z[rt].sze += z[z[rt].ch[0]].sze; if (z[rt].ch[1]) z[rt].sum += z[z[rt].ch[1]].sum, z[rt].sze += z[z[rt].ch[1]].sze; if (z[rt].ch[0] && z[rt].ch[1]) { z[rt].lsum = max(z[z[rt].ch[0]].lsum, z[z[rt].ch[0]].sum + z[rt].x + z[z[rt].ch[1]].lsum); z[rt].rsum = max(z[z[rt].ch[1]].rsum, z[z[rt].ch[1]].sum + z[rt].x + z[z[rt].ch[0]].rsum); z[rt].msum = max(max(z[z[rt].ch[0]].msum, z[z[rt].ch[1]].msum), z[z[rt].ch[0]].rsum + z[z[rt].ch[1]].lsum + z[rt].x); } else if (z[rt].ch[0]) { z[rt].lsum = max(max(z[z[rt].ch[0]].lsum, z[z[rt].ch[0]].sum + z[rt].x), 0ll); z[rt].rsum = max(z[z[rt].ch[0]].rsum + z[rt].x, 0ll); z[rt].msum = max(z[z[rt].ch[0]].msum, z[z[rt].ch[0]].rsum + z[rt].x); } else if (z[rt].ch[1]) { z[rt].lsum = max(z[z[rt].ch[1]].lsum + z[rt].x, 0ll); z[rt].rsum = max(max(z[z[rt].ch[1]].rsum, z[z[rt].ch[1]].sum + z[rt].x), 0ll); z[rt].msum = max(z[z[rt].ch[1]].msum, z[z[rt].ch[1]].lsum + z[rt].x); } else { z[rt].lsum = z[rt].rsum = max(z[rt].x, 0ll); z[rt].msum = z[rt].x; } } int cnt; inline int newnode(int v = 0) { z[++cnt].x = z[cnt].msum = z[cnt].sum = v; z[cnt].lsum = z[cnt].rsum = max(v, 0); z[cnt].sze = 1; z[cnt].pri = rand(); return cnt; } inline int merge(int x, int y) { if(!x || !y) return x + y; if(z[x].pri < z[y].pri) { z[x].ch[1] = merge(z[x].ch[1], y); update(x); return x; } else { z[y].ch[0] = merge(x, z[y].ch[0]); update(y); return y; } } inline void split(int rt, int k, int &x, int &y) { if(!rt) x = y = 0; else { if(k <= z[z[rt].ch[0]].sze) { y = rt, split(z[rt].ch[0], k, x, z[rt].ch[0]); } else { x = rt, split(z[rt].ch[1], k - z[z[rt].ch[0]].sze - 1, z[rt].ch[1], y); } update(rt); } } int n, m, xx, yy, zz, rot; inline void debug() { go(rt, 1, cnt, 1) { printf("%d: pri:%d, sze:%d, ch[0]:%d, ch[1]:%d, x:%d\n", rt, z[rt].pri, z[rt].sze, z[rt].ch[0], z[rt].ch[1], z[rt].x); } printf("\n"); } int main() { srand((unsigned)time(NULL)); n = read(); go(i, 1, n, 1) { int x = read(); split(rot, i, xx, yy); rot = merge(merge(xx, newnode(x)), yy); } m = read(); go(i, 1, m, 1) { char s; cin >> s; int x = read(), v; if(s == 'I') { v = read(); split(rot, x - 1, xx, yy); rot = merge(merge(xx, newnode(v)), yy); } else if(s == 'D') { split(rot, x, xx, zz); split(xx, x - 1, xx, yy); yy = merge(z[yy].ch[0], z[yy].ch[1]); rot = merge(merge(xx, yy), zz); } else if(s == 'R') { v = read(); split(rot, x, xx, zz); split(xx, x - 1, xx, yy); z[yy].x = v; z[yy].sum = z[yy].msum = v; z[yy].lsum = z[yy].rsum = max(v, 0); rot = merge(merge(xx, yy), zz); } else if(s == 'Q') { v = read(); split(rot, v, xx, zz); split(xx, x - 1, xx, yy); printf("%lld\n", z[yy].msum); rot = merge(merge(xx, yy), zz); } } return 0; }
希望可以帮到WA了半天数组开小或者没开long long的同学
(我可是因为这两个调了一天啊QAQ)