题目传送门(BZOJ)
>原文链接<

题解 :

我们把操作分开讲 :

  1. 考虑到本题的查询与修改操作,除了 Splay 需要维护的基本信息,我们需要对每个节点维护如下信息 :
    laz[p] // 这个点的所有子节点将要修改成 laz[p]tag[p] // 区间反转标记mxn[p] // 这个节点与其子树的最大连续子段和mxl[p] // 必须包含左端点的最大连续子段和, 用来区间合并更新 mxnmxr[p] // 必须包含右端点的最大连续子段和, 用来区间合并更新 mxnsum[p] // 子树权值和
  2. 插入

    为了保证插入的复杂度, 我们利用插入区间是连续的特性,在 posi 处直接 O(tot) 建树

    具体操作为 :

    令 `x = posi, p = x+1` 先将 x 旋转到根, 然后将 p 旋转到根的儿子,这时候 p 是没有左子树的,我们以 p 为根结点,直接把所有需要插入的点建树插在 p 上, 然后 `pushUp`
  3. 删除

    由于空间的原因,我们在删除时要进行内存回收,先找出这棵子树,然后递归删除,同时把节点信息清空,编号压栈,在需要开新节点的时候直接读取栈顶编号。

    具体操作为 :

    ​ 令 x = posi, p = posi+tot+1 先将 x 旋转到根, 然后将 p 旋转到根的儿子,这时候 p 的左子树是我们要删除的子树,递归整棵子树进行删除即可

  4. 修改

    具体操作 :按照删除操作的方法找出这棵大小为 tot 的子树,然后修改父节点、并给父节点打上标记

  5. 翻转

    一般的 Splay 区间反转即可

  6. 求和

    具体操作 : 按照删除的方法找出这棵子树,然后读取这个节点的 sum

  7. 求最大连续子段和

    具体操作 : 按照删除的方法找出这棵子树, 然后读取这个节点的 mxn

  8. pushDown/pushUp 具体操作见代码。

代码 :

#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#define ls ch[p][0]#define rs ch[p][1]#define get(x) (ch[f[x]][1] == x)using namespace std;const int N = 1100000;const int INF = 0x3f3f3f3f;int n, m;int a[N], val[N], tag[N], ch[N][2], siz[N], f[N], root, laz[N], sum[N], maxn[N], maxl[N], maxr[N];int s[N], top, cnt;int rt, sz;class Splay {private: void clear(int p) { ls = rs = val[p] = tag[p] = siz[p] = f[p] = sum[p] =maxn[p] = maxl[p] = maxr[p] = 0; laz[p] = INF; } int newnode(int v) { int p; if(top) p = s[top--]; else p = ++cnt; clear(p); val[p] = v;siz[p] = 1; maxl[p] = maxr[p] = v>0?v:0; maxn[p] = v; return p; }public: void pushdown(int p) { if(laz[p]!=INF) { int t = laz[p]; laz[p]=INF; laz[ls]=laz[rs]=t; val[ls]=val[rs]=t; sum[ls]=siz[ls]*t; sum[rs]=siz[rs]*t; maxl[ls]=maxr[ls]=t>0?sum[ls]:0; maxn[ls]=t>0?sum[ls]:t; maxl[rs]=maxr[rs]=t>0?sum[rs]:0; maxn[rs]=t>0?sum[rs]:t; } if(tag[p]) { tag[p]=0; swap(ls, rs); swap(maxl[ls], maxr[ls]); swap(maxl[rs], maxr[rs]); tag[ls]^=1, tag[rs]^=1; } } void up(int p) { if(!p)return ; siz[p] = siz[ls]+siz[rs]+1; sum[p] = sum[ls]+sum[rs]+val[p]; maxl[p] = max(maxl[ls], sum[ls]+val[p]+maxl[rs]); maxr[p] = max(maxr[rs], sum[rs]+val[p]+maxr[ls]); maxn[p] = val[p]; maxn[p] = max(max(maxn[p], maxn[ls]), maxn[rs]); maxn[p] = max(maxn[p], maxr[ls]+val[p]+maxl[rs]); } int find(int x) { int p = root; while(true) { pushdown(p); if(x<=siz[ls]) p = ls; else { x-=siz[ls]+1; if(!x) return p; p = rs; } } } void Rotate(int x) { int y = f[x], z = f[y], k = get(x); ch[y][k] = ch[x][k^1], f[ch[y][k]] = y; ch[x][k^1] = y; f[y] = x, f[x] = z; if(z) ch[z][ch[z][1] == y] = x; up(y), up(x); if(root==y) root = x; return; } void splay(int x, int y) { for(int fa; (fa = f[x]) != y; Rotate(x)) if(f[fa] != y) Rotate(get(x) == get(fa) ? fa : x); return ; } void build(int fa, int l, int r, int k) { if(l>r) return; int mid = (l+r) >> 1; int p = newnode(a[mid]); ch[fa][k] = p; f[p] = fa; build(p, l, mid-1, 0); build(p, mid+1, r, 1); up(p); } void Insert() { int x, y; scanf("%d%d", &x, &y); x+=1; sz += y; for(int i=1;i<=y;i++) scanf("%d", &a[i]); int p = x+1; x = find(x), p = find(p); splay(x, f[root]);splay(p, root); build(p, 1, y, 0); } void rec(int p) { if(!p)return ; if(ls)rec(ls); ls = 0; if(rs)rec(rs); rs = 0; s[++top] = p; } void Del() { int x, p; scanf("%d%d", &x, &p); p+=x+1; x = find(x), p = find(p); splay(x, f[root]); splay(p, root); sz-=siz[ls]; rec(ls); ls = 0; up(p); up(x); } void Reverse() { int x, p; scanf("%d%d", &x, &p); p+=x+1; x = find(x), p = find(p); splay(x, f[root]); splay(p, root); tag[ls]^=1; swap(maxl[ls], maxr[ls]); up(p), up(x); } int Sum() { int x, p; scanf("%d%d", &x, &p); p+=x+1; x = find(x), p = find(p); splay(x, f[root]); splay(p, root); return sum[ls]; } void Change() { int x, p, c; scanf("%d%d%d", &x, &p, &c); p+=x+1; x = find(x), p = find(p); splay(x, f[root]); splay(p, root); laz[ls] = c; val[ls] = c; sum[ls] = c*siz[ls]; maxl[ls]=maxr[ls]=c>0?sum[ls]:0; maxn[ls]=c>0?sum[ls]:c; up(p), up(x); } int Getmax() { int x=1, p=sz; x=find(x), p=find(p); splay(x, f[root]); splay(p, root); return maxn[ls]; }}Tr;struct prt { int p, val; bool operator < (const prt &a) const { return p<a.p; }}pp[N];int tot;class Init_ { void build(int fa, int l, int r) { if(l>r) return ; int mid = (l+r) >> 1; val[mid] = a[mid-1]; ch[fa][mid>fa] = mid; siz[mid] = 1; f[mid] = fa; build(mid, l, mid-1); build(mid, mid+1, r); Tr.up(mid); }public: void Init() { memset(laz, 0x3f, sizeof(laz)); scanf("%d%d", &n, &m); sz = cnt = n+2; for(int i=1;i<=n;i++) scanf("%d", &a[i]); build(0, 1, n+2); root = (n+3)>>1; } void Solve() { for(int i=1;i<=m;i++) { char opt[10]; scanf("%s", opt); if(opt[0]=='I') Tr.Insert(); else if(opt[0]=='D') Tr.Del(); else if(opt[0]=='R') Tr.Reverse(); else if(opt[0]=='G') printf("%d\n", Tr.Sum()); else if(opt[2]=='K') Tr.Change(); else printf("%d\n", Tr.Getmax()); } }}IAS;int main() { IAS.Init(); IAS.Solve();}

end