1500: [NOI2005]维修数列
Time Limit: 10 Sec Memory Limit: 64 MBSubmit: 15834 Solved: 5252
[Submit][Status][Discuss]
Description
Input
输入的第1 行包含两个数N 和M(M ≤20 000)，N 表示初始时数列中数的个数，M表示要进行的操作数目。
第2行包含N个数字，描述初始时的数列。
以下M行，每行一条命令，格式参见问题描述中的表格。
任何时刻数列中最多含有500 000个数，数列中任何一个数字均在[-1 000, 1 000]内。
插入的数字总数不超过4 000 000个，输入文件大小不超过20MBytes。
Output
对于输入数据中的GET-SUM和MAX-SUM操作，向输出文件依次打印结果，每个答案（数字）占一行。
Sample Input
9 8
2 -6 3 5 1 -5 -3 6 3
GET-SUM 5 4
MAX-SUM
INSERT 8 3 -5 7 2
DELETE 12 1
MAKE-SAME 3 3 2
REVERSE 3 6
GET-SUM 5 4
MAX-SUM
2 -6 3 5 1 -5 -3 6 3
GET-SUM 5 4
MAX-SUM
INSERT 8 3 -5 7 2
DELETE 12 1
MAKE-SAME 3 3 2
REVERSE 3 6
GET-SUM 5 4
MAX-SUM
Sample Output
-1
10
1
10
10
1
10
HINT
分析：比较烦人的一道题.有两点需要特别注意：1.每次del的点要放到栈里面，不能无限加点，这样会MLE. 2.最后max-sum操作所求的序列至少要有1个元素，也就是说一个全是负数的序列的答案不是0！
如何解决这两个问题？对于第一个问题，在建树的时候如果栈里还有多余的点，取出来就好了. 对于第二个问题，在开始将所有的lmax,rmax,ans初始化为-inf.每次pushup要么只求一个子树的答案，要么求跨过当前根的两个子树的答案.并且覆盖操作要特判覆盖的数是不是负数，如果是则必须选其中一个数作为lmax,rmax,ans.
剩下的都是模板问题了，和线段树非常像.
#include <stack> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; const int maxn = 500010,inf = 707406378; stack <int> s; int n,m,a[maxn],root,tot,sizee[maxn]; struct node { int fa,left,right,v,sum,ans,lmax,rmax,tag,cnt; }e[maxn]; void pushup(int x) { sizee[x] = 1 + sizee[e[x].left] + sizee[e[x].right]; e[x].sum = e[e[x].left].sum + e[e[x].right].sum + e[x].v; e[x].lmax = max(e[e[x].left].lmax,e[e[x].left].sum + e[x].v + max(0,e[e[x].right].lmax)); e[x].rmax = max(e[e[x].right].rmax,e[e[x].right].sum + e[x].v + max(0,e[e[x].left].rmax)); e[x].ans = max(e[e[x].left].ans,e[e[x].right].ans); e[x].ans = max(e[x].ans,max(e[e[x].left].rmax,0) + e[x].v + max(0,e[e[x].right].lmax)); } void fan(int x) { int t = e[x].lmax; e[x].lmax = e[x].rmax; e[x].rmax = t; t = e[x].left; e[x].left = e[x].right; e[x].right = t; e[x].tag ^= 1; } void cover(int x,int y) { e[x].sum = sizee[x] * y; e[x].v = y; e[x].maxx = y; if (y <= 0) e[x].lmax = e[x].rmax = e[x].ans = y; else e[x].lmax = e[x].rmax = e[x].ans = y * sizee[x]; e[x].cnt = 1; } void pushdown(int x) { if (e[x].tag) { if (e[x].left) fan(e[x].left); if (e[x].right) fan(e[x].right); e[x].tag = 0; } if (e[x].cnt) { if (e[x].left) cover(e[x].left,e[x].v); if (e[x].right) cover(e[x].right,e[x].v); e[x].cnt = 0; } } void build(int l,int r,int &x,int y) { if (l > r) return; if (!x) { if (!s.empty()) { x = s.top(); s.pop(); } else x = ++tot; } int mid = (l + r) >> 1; e[x].v = a[mid]; e[x].fa = y; build(l,mid - 1,e[x].left,x); build(mid + 1,r,e[x].right,x); pushup(x); } void turnr(int x) { pushdown(x); int y = e[x].fa; int z = e[y].fa; e[y].left = e[x].right; if (e[x].right != 0) e[e[x].right].fa = y; e[x].fa = z; if (z != 0) { if (e[z].left == y) e[z].left = x; else e[z].right = x; } e[x].right = y; e[y].fa = x; pushup(x); pushup(y); } void turnl(int x) { pushdown(x); int y = e[x].fa; int z = e[y].fa; e[y].right = e[x].left; if (e[x].left != 0) e[e[x].left].fa = y; e[x].fa = z; if (z != 0) { if (e[z].left == y) e[z].left = x; else e[z].right = x; } e[x].left = y; e[y].fa = x; pushup(x); pushup(y); } void splay(int x,int yy) { while (e[x].fa != yy) { pushdown(x); int y = e[x].fa; int z = e[y].fa; if (z == 0 || z == yy) { if (e[y].left == x) turnr(x); else turnl(x); } else { if (e[z].left == y && e[y].left == x) { turnr(y); turnr(x); } else { if (e[z].right == y && e[y].right == x) { turnl(y); turnl(x); } else { if (e[z].left == y && e[y].right == x) { turnl(x); turnr(x); } else { turnr(x); turnl(x); } } } } } if (yy == 0) root = x; pushup(x); } int find(int x,int k) { pushdown(x); if (k > sizee[e[x].left] + 1) return find(e[x].right,k - 1 - sizee[e[x].left]); if (k == sizee[e[x].left] + 1) return x; return find(e[x].left,k); } void del(int x) { if (!x) return; s.push(x); del(e[x].left); del(e[x].right); sizee[x] = e[x].left = e[x].right = e[x].cnt = e[x].tag = e[x].fa = e[x].sum = e[x].v = 0; e[x].maxx = e[x].lmax = e[x].rmax = e[x].ans = -inf; } int main() { for (int i = 0; i < maxn; i++) e[i].lmax = e[i].rmax = e[i].ans = -inf; scanf("%d%d",&n,&m); for (int i = 1; i <= n; i++) scanf("%d",&a[i]); build(0,n + 1,root,0); root = 1; for (int i = 1; i <= m; i++) { char s[15]; scanf("%s",s); if (s[0] == 'I') { int x,y; scanf("%d%d",&x,&y); for (int j = 1; j <= y; j++) scanf("%d",&a[j]); int p = find(root,x + 1),q = find(root,x + 2); splay(p,0); splay(q,p); build(1,y,e[q].left,q); pushup(q); pushup(p); } if (s[0] == 'D') { int x,y; scanf("%d%d",&x,&y); int p = find(root,x),q = find(root,x + y + 1); splay(p,0); splay(q,p); del(e[q].left); e[q].left = 0; pushup(q); pushup(p); } if (s[0] == 'M' && s[2] == 'K') { int x,y,z; scanf("%d%d%d",&x,&y,&z); int p = find(root,x),q = find(root,x + y + 1); splay(p,0); splay(q,p); cover(e[q].left,z); pushup(q); pushup(p); } if (s[0] == 'R') { int x,y; scanf("%d%d",&x,&y); int p = find(root,x),q = find(root,x + y + 1); splay(p,0); splay(q,p); if (e[q].left && !e[e[q].left].tag) fan(e[q].left); pushup(q); pushup(p); } if (s[0] == 'G') { int x,y; scanf("%d%d",&x,&y); int p = find(root,x),q = find(root,x + y + 1); splay(p,0); splay(q,p); printf("%d ",e[e[q].left].sum); } if (s[0] == 'M' && s[2] == 'X') { int p = find(root,1),q = find(root,sizee[root]); splay(p,0); splay(q,p); printf("%d ",e[e[q].left].ans); } } return 0; }