BZOJ 1500([NOI2005]检修数列-Splay的数列维护)

1500: [NOI2005]维修数列

Input输入文件的第1行包含两个数N和M，N表示初始时数列中数的个数，M表示要进行的操作数目。 第2行包含N个数字，描述初始时的数列。 以下M行，每行一条命令，格式参见问题描述中的表格。

Output对于输入数据中的GET-SUM和MAX-SUM操作，向输出文件依次打印结果，每个答案（数字）占一行。

Sample Input9 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

Splay解决数列维护。

推荐：用伸展树解决数列维护问题

#include<cstdio>#include<cstring>#include<algorithm>#include<functional>#include<iostream>#include<cstdlib>#include<cmath>using namespace std;#define MAXN (500000+10)#define MAXM (20000+10)#define INF (0xfffffff)struct node{int value,MaxL,MaxR,MaxM,sum,size;bool rev,same;node *ch[2],*pre;node(node *f,int _value,int _MaxL,int _MaxR,int _MaxM,int _sum,int _size):value(_value),MaxL(_MaxL),MaxR(_MaxR),MaxM(_MaxM),sum(_sum),size(_size){rev=same=0,pre=f,ch[0]=ch[1]=NULL;}node(){rev=same=0;}int l_siz(){if (ch[0]) return ch[0]->size;else return 0;}//int r_siz(){return (ch[1])?ch[1]->size:0;}friend void pushdown(node *x){if (x){if (x->rev){x->rev=0;if (x->ch[0]) x->ch[0]->rev^=1;if (x->ch[1]) x->ch[1]->rev^=1;swap(x->ch[0],x->ch[1]);swap(x->MaxL,x->MaxR);}if (x->same){x->same=0;if (x->ch[0]) {x->ch[0]->same=1;x->ch[0]->value=x->value;x->ch[0]->sum=x->value*x->ch[0]->size;x->ch[0]->MaxL=x->ch[0]->MaxR=x->ch[0]->MaxM=max(x->value,x->ch[0]->sum);}if (x->ch[1]) {x->ch[1]->same=1;x->ch[1]->value=x->value;x->ch[1]->sum=x->value*x->ch[1]->size;x->ch[1]->MaxL=x->ch[1]->MaxR=x->ch[1]->MaxM=max(x->value,x->ch[1]->sum);}}}}friend void update(node *x){if (x){pushdown(x->ch[0]);pushdown(x->ch[1]); //由于有坑爹的rev操作，必须先down. x->size=((x->ch[0])?x->ch[0]->size:0)+((x->ch[1])?x->ch[1]->size:0)+1;x->sum=((x->ch[0])?x->ch[0]->sum:0)+((x->ch[1])?x->ch[1]->sum:0)+x->value;x->MaxL=max(((x->ch[0])?x->ch[0]->MaxL:x->value),((x->ch[0])?x->ch[0]->sum:0)+x->value+max(0,((x->ch[1])?x->ch[1]->MaxL:0)));x->MaxR=max(((x->ch[1])?x->ch[1]->MaxR:x->value),((x->ch[1])?x->ch[1]->sum:0)+x->value+max(0,((x->ch[0])?x->ch[0]->MaxR:0)));//cout<<((x->ch[1])?x->ch[1]->MaxR:x->value)<<' '<<+max(0,(((x->ch[0])?x->ch[0]->MaxR:0)))<<endl;x->MaxM=max(max(((x->ch[0])?x->ch[0]->MaxM:x->value),((x->ch[1])?x->ch[1]->MaxM:x->value)),((x->ch[0])?max(x->ch[0]->MaxR,0):0)+((x->ch[1])?max(x->ch[1]->MaxL,0):0)+x->value);}}};node *q[MAXN];int q_siz=0;int n,m,a[MAXN];node* newnode(node *f,int value,int MaxL,int MaxR,int MaxM,int sum,int size){if (q_siz){q[q_siz]->value=value;q[q_siz]->MaxL=MaxL;q[q_siz]->MaxR=MaxR;q[q_siz]->MaxM=MaxM;q[q_siz]->sum=sum;q[q_siz]->size=size;q[q_siz]->rev=q[q_siz]->same=0;q[q_siz]->pre=f;q[q_siz]->ch[0]=q[q_siz]->ch[1]=NULL;return q[q_siz--];}node *x=new node(f,value,MaxL,MaxR,MaxM,sum,size);return x;}node* newnode(){if (q_siz) return q[q_siz--];node *x=new node();return x;}void addnode(node *x){q[++q_siz]=x;*x=node();}struct Splay{node *root;Splay(){root=newnode(NULL,-INF,-INF,-INF,-INF,0,2);root->ch[0]=newnode(root,-INF,-INF,-INF,-INF,0,1);}void Print(node *x){if (x->ch[0]) {cout<<"(",Print(x->ch[0]),cout<<")-";}cout<<x->same;if (x->ch[1]) cout<<"-(",Print(x->ch[1]),cout<<")";}void rotate(node *x,int c) //0左旋 1右旋 {node *y=x->pre;pushdown(y),pushdown(x);y->ch[!c]=x->ch[c];if (x->ch[c]!=NULL) x->ch[c]->pre=y;x->pre=y->pre;if (y->pre!=NULL){if (y->pre->ch[0]==y) y->pre->ch[0]=x;else y->pre->ch[1]=x;}x->ch[c]=y;y->pre=x;if (y==root) root=x;update(y);}void splay(node *x,node *f){for(pushdown(x);x->pre!=f;){if (x->pre->pre==f){if (x->pre->ch[0]==x) rotate(x,1);else rotate(x,0);}else{node *y=x->pre,*z=y->pre;pushdown(z);pushdown(y);pushdown(x); //rev改变树结构 if (y->ch[0]==x&&z->ch[0]==y) rotate(y,1),rotate(x,1);else if (y->ch[1]==x&&z->ch[1]==y) rotate(y,0),rotate(x,0);else if (y->ch[0]==x&&z->ch[1]==y) rotate(x,1),rotate(x,0);else if (y->ch[1]==x&&z->ch[0]==y) rotate(x,0),rotate(x,1);}update(x);//Print(root);cout<<endl;}} node* find_kth(node *x,int k){pushdown(x); //确保x正确 if (x->l_siz()>=k) return find_kth(x->ch[0],k);if (x->l_siz()+1==k) return x;else return find_kth(x->ch[1],k-x->l_siz()-1);}void build(node *f,node *x,int l,int r){if (l>r) return;int m=(l+r)>>1;*x=node(f,a[m],a[l],a[r],a[m],a[m],1);if (l<m) build(x,x->ch[0]=newnode(),l,m-1);if (m<r) build(x,x->ch[1]=newnode(),m+1,r);if (l<r) update(x);}void del(node *x){if (x->ch[0]) del(x->ch[0]);if (x->ch[1]) del(x->ch[1]);addnode(x);}void insert(int pos,int tot){splay(find_kth(root,pos+1),NULL);splay(find_kth(root,pos+2),root);root->ch[1]->ch[0]=newnode();build(root->ch[1],root->ch[1]->ch[0],1,tot);update(root->ch[1]);update(root);}void delet(int pos,int tot){splay(find_kth(root,pos),NULL);splay(find_kth(root,pos+1+tot),root);//Print(root);del(root->ch[1]->ch[0]);root->ch[1]->ch[0]=NULL;update(root->ch[1]);update(root);}void reverse(int pos,int tot){splay(find_kth(root,pos),NULL);splay(find_kth(root,pos+1+tot),root);root->ch[1]->ch[0]->rev^=1;update(root->ch[1]);update(root);}void make_same(int pos,int tot,int c){splay(find_kth(root,pos),NULL);splay(find_kth(root,pos+1+tot),root);node *x=root->ch[1]->ch[0];x->same=1;x->value=c;x->sum=c*x->size;x->MaxL=x->MaxR=x->MaxM=max(x->value,x->sum);update(root->ch[1]);update(root);}void get_sum(int pos,int tot){if (tot==0){printf("0\n");return;}splay(find_kth(root,pos),NULL);//Print(root);cout<<endl;splay(find_kth(root,pos+1+tot),root);//Print(root);cout<<endl;node *x=root->ch[1]->ch[0];printf("%d\n",x->sum);}void max_sum(){splay(find_kth(root,1),NULL);splay(find_kth(root,root->size),root);printf("%d\n",root->ch[1]->ch[0]->MaxM);}}S;int main(){//freopen("bzoj1500.in","r",stdin);cin>>n>>m;for (int i=1;i<=n;i++) cin>>a[i];S.insert(0,n);//S.Print(S.root);cout<<endl;for (int i=1;i<=m;i++){//cout<<i<<':';char s[10];scanf("%s",s);switch (s[2]){case'S':{int pos,tot;scanf("%d%d",&pos,&tot);for (int i=1;i<=tot;i++) scanf("%d",&a[i]);S.insert(pos,tot);break;}case'L':{int pos,tot;scanf("%d%d",&pos,&tot);S.delet(pos,tot);break;}case'K':{int pos,tot,c;scanf("%d%d%d",&pos,&tot,&c);S.make_same(pos,tot,c);break;}case'V':{int pos,tot;scanf("%d%d",&pos,&tot);S.reverse(pos,tot);break;}case'T':{int pos,tot;scanf("%d%d",&pos,&tot);S.get_sum(pos,tot);break;}case'X':{S.max_sum();break;}}//S.Print(S.root);cout<<endl;}return 0;}