bzoj1500 [NOI2005]维修数列

传送门 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

Sample Output

-1

10

1

10

HINT

Source

题解

我们可以用一个单词来很好地描述这道题：eggache 【这个词是我自创的，但是百度翻译居然能翻译出来？好迷啊

这道题真的是所有splay题目中的毒瘤啊

第二个点总是过不了，找了半天终于发现：只有COGS能下数据！ 【这个人为什么不好好找错啊 //洛谷说数据太大了下不了好迷啊

用时： 04.09:上午9:20~11:40,下午1:50~5:00,晚上6:20~10:00 04.10:上午7:00~8:40,9:40~11:40 04.12:上午8:00~10:00 共计14h50min

终于还是把这道题A掉了！happy~

让我们分析一下这道题：

首先看到内存限制64MB，说明这道题需要很好地利用所有的空间，所以要进行回收内存 然后看到题目要求支持6种操作，对应的做法是：

注： #define ① 将位置为pos的节点splay到根上，将位置为pos+1的节点splay到根的右儿子上 #define ② 将位置为l-1的节点splay到根上，将位置为r+1的节点splay到根的右儿子上 #define ③(now) 将now接到根的右儿子的左儿子上 #define ④ 根节点的右儿子的左儿子 int main() { printf("在下面所有的解释中，所有的数字编号都已被进行宏定义，请注意\n"); }

1.INSERT：将所有要插入的新的数字建成一颗小的splay，①，将它的根接到原有的splay中，即③(小splay的根)

2.DELETE：②，对④（即我们要删除的区间）进行一遍dfs，将其中所有的内存进行回收（我们可以使用循环队列、STL或者栈记录回收节点在内存池中的编号/下标来实现），然后将④设为null

3.MAKE-SAME：②，将④的num值设为新值，对其所有祖先update，并对其打上标记，以后用其num值来更新子树

4.REVERSE：②，将④的左右儿子、左右max值进行交换，并更新标记（0->1,1->0）

5.GET-SUM：②，返回④的sum值

6.MAX-SUM：返回④的maxn值

//一开始看确实有些不舒服，但是习惯了或者理解了就好了 不要给自己省字数找理由

WARNING：注意update，注意null，注意哨兵节点的各种数据的处理！

CODE：

#include<cstdio> const int INF=2000; inline int max(int a,int b){if(a>=b)return a;return b;} inline int min(int a,int b){if(a<=b)return a;return b;} inline void swap(int &a,int &b){a^=b;b^=a;a^=b;} struct stack { int t; int a[500010]; inline void clear(){t=-1;} inline void push(int &n){a[++t]=n;} inline int top(){return a[t];} inline void pop(){t--;} inline bool empty(){return t<0;} }reuse; struct node { int num,size,lmax,rmax,maxn,sum,id,rev; bool change; node *ch[2],*fa; inline void update() { size=ch[0]->size+ch[1]->size+1; sum=ch[0]->sum+ch[1]->sum; if(num!=-INF) sum+=num; lmax=max(ch[0]->lmax,max(ch[0]->sum+num,ch[0]->sum+ch[1]->lmax+num)); rmax=max(ch[1]->rmax,max(ch[1]->sum+num,ch[1]->sum+ch[0]->rmax+num)); maxn=max(ch[0]->maxn,ch[1]->maxn); maxn=max(maxn,max(ch[0]->rmax+num,ch[1]->lmax+num)); maxn=max(maxn,max(ch[0]->rmax+ch[1]->lmax+num,num)); } inline int getwh() { if(fa->ch[0]==this) return 0;return 1; } inline void pushchange(int n) { num=n; sum=size*n; maxn=lmax=rmax=max(num,sum); change=1; } inline void pushrev() { swap(lmax,rmax); node *tmp=ch[0];ch[0]=ch[1];ch[1]=tmp; rev^=1; } inline void setch(int wh,node *child); inline void pushdown(); }pool[500010],*root,*null,*newroot; inline void node::setch(int wh,node *child) { ch[wh]=child; if(child!=null) child->fa=this; update(); } inline void node::pushdown() { if(rev) { if(ch[0]!=null) ch[0]->pushrev(); if(ch[1]!=null) ch[1]->pushrev(); rev=0; } if(change) { if(ch[0]!=null) ch[0]->pushchange(num); if(ch[1]!=null) ch[1]->pushchange(num); change=0; } } char s[10]; int a[500010]; int n,m,tot,x,y,z; inline void read(int &n) { n=0;char c=getchar();bool b=0; while(c<'0'||c>'9'){if(c=='-')b=1;c=getchar();} while(c>='0'&&c<='9') n=n*10+c-48,c=getchar(); if(b) n*=-1; } inline void getstring() { int p=-1; char c=getchar(); while((c<'A'||c>'Z')&&c!='-') c=getchar(); while((c>='A'&&c<='Z')||c=='-') s[++p]=c,c=getchar(); } inline node *getnew(int num) { node *now; if(!reuse.empty()) now=pool+reuse.top(),now->id=reuse.top(),reuse.pop(); else now=pool+ ++tot,now->id=tot; now->ch[0]=now->ch[1]=now->fa=null; now->num=now->sum=now->maxn=now->lmax=now->rmax=num; if(num==-1e9) now->sum=0; now->size=1; now->change=now->rev=0; return now; } inline void rotate(node *now) { node *fa=now->fa,*grand=now->fa->fa; int wh=now->getwh(); fa->setch(wh,now->ch[wh^1]); now->setch(wh^1,fa); now->fa=grand; if(grand!=null) { if(grand->ch[0]==fa) grand->ch[0]=now; else grand->ch[1]=now; } } inline void splay(node *now,node *tar) { for(;now->fa!=tar;rotate(now)) if(now->fa->fa!=tar) { if(now->getwh()==now->fa->getwh()) rotate(now->fa); else rotate(now); } if(tar==null) root=now; } node *build(int l,int r) { int mid=(l+r)>>1; node *now=getnew(a[mid]); if(l<mid) now->setch(0,build(l,mid-1)); if(r>mid) now->setch(1,build(mid+1,r)); return now; } inline node *kth(int rank) { node *now=root; int ranking=0; while(now!=null) { now->pushdown(); int tmp=ranking+now->ch[0]->size; if(tmp+1==rank) return now; if(tmp+1>rank) now=now->ch[0]; else ranking=tmp+1,now=now->ch[1]; } } inline void insert(node *newone,int pos) { splay(kth(pos),null); splay(kth(pos+1),root); root->ch[1]->setch(0,newone); root->update(); } void dfs(node *now) { reuse.push(now->id); if(now->ch[0]!=null) dfs(now->ch[0]); if(now->ch[1]!=null) dfs(now->ch[1]); } inline void del(int pos,int n) { splay(kth(pos-1),null); splay(kth(pos+n),root); dfs(root->ch[1]->ch[0]); root->ch[1]->setch(0,null); root->update(); } inline void changenum(int pos,int n,int num) { splay(kth(pos-1),null); splay(kth(pos+n),root); root->ch[1]->ch[0]->pushchange(num); root->ch[1]->update(); root->update(); } inline void reverse(int pos,int n) { splay(kth(pos-1),null); splay(kth(pos+n),root); root->ch[1]->ch[0]->pushrev(); root->ch[1]->update(); root->update(); } inline int sum(int pos,int n) { splay(kth(pos-1),null); splay(kth(pos+n),root); return root->ch[1]->ch[0]->sum; } int main() { read(n),read(m); null=pool; null->ch[0]=null->ch[1]=null->fa=null; null->lmax=null->rmax=null->maxn=-INF; root=null; reuse.clear(); for(register int i=1;i<=n;i++) read(a[i]); a[0]=a[n+1]=-INF; root=build(0,n+1); while(m--) { getstring(); if(s[0]=='I') { read(x),read(y); for(register int i=1;i<=y;i++) read(a[i]); newroot=build(1,y); insert(newroot,x+1); } else if(s[0]=='D') read(x),read(y),del(x+1,y); else if(s[2]=='K') read(x),read(y),read(z),changenum(x+1,y,z); else if(s[0]=='R') read(x),read(y),reverse(x+1,y); else if(s[0]=='G') read(x),read(y),printf("%d\n",sum(x+1,y)); else printf("%d\n",root->maxn); } return 0; }