1500: [NOI2005]维修数列题目链接：http://61.187.179.132/JudgeOnline/problem.php?id1500题目思路：splay
1500: [NOI2005]维修数列
题目链接：http://61.187.179.132/JudgeOnline/problem.php?id=1500
题目思路：splay ,包括区间插入，区间删除，回收内存，区间反转，区间和，区间最大子段，成段更新等操作。
#include<stdio.h>#include<stdlib.h>#include<string.h>#include<string>#include<queue>#include<algorithm>#include<vector>#include<stack>#include<list>#include<iostream>#include<map>using namespace std;#define inf 0x3f3f3f3f#define Max 110#define M 501000#define keytree ch[ch[root][1]][0]int max(int a,int b){return a>b?a:b;}int min(int a,int b){return a<b?a:b;}int p[M],ch[M][2],v[M],s[M],lm[M],rm[M],ma[M],same[M],rev[M],sum[M],vst[M],a[M];int top1,top2,root,n,m;void visit(int x){ if(!x) return; // printf(" x %d p %d ch0 %d ch1 %d v %d s %d rev %d sum %d lm %d rm %d ma %d \n", // x,p[x],ch[x][0],ch[x][1],v[x],s[x],rev[x],sum[x],lm[x],rm[x],ma[x]); vst[++top2]=x; visit(ch[x][0]); visit(ch[x][1]);}void up(int x){ int l=ch[x][0],r=ch[x][1]; s[x]=1+s[l]+s[r]; sum[x]=sum[l]+v[x]+sum[r]; lm[x]=max(lm[l],sum[l]+v[x]+max(0,lm[r])); rm[x]=max(rm[r],sum[r]+v[x]+max(0,rm[l])); ma[x]=max(0,rm[l])+v[x]+max(0,lm[r]); ma[x]=max(ma[x],max(ma[l],ma[r]));}void datasame(int x,int val){ if(!x) return; same[x]=1; v[x]=val; sum[x]=s[x]*val; lm[x]=rm[x]=ma[x]=max(val,sum[x]);}void datarev(int x){ if(!x) return; rev[x]^=1; swap(lm[x],rm[x]); swap(ch[x][0],ch[x][1]);}void down(int x){ int l=ch[x][0],r=ch[x][1]; if(same[x]) { datasame(l,v[x]); datasame(r,v[x]); } if(rev[x]) { datarev(l); datarev(r); } same[x]=rev[x]=0;}void newnode(int &x,int val,int pre){ if(top2) x=vst[top2--]; else x=++top1; p[x]=pre; s[x]=1; ch[x][0]=ch[x][1]=same[x]=rev[x]=0; lm[x]=rm[x]=ma[x]=v[x]=sum[x]=val;}void build(int &x,int l,int r ,int pre){ if(l>r)return; int mid=(l+r)>>1; newnode(x,a[mid],pre); build(ch[x][0],l,mid-1,x); build(ch[x][1],mid+1,r,x); up(x);}void init(){ top1=top2=p[0]=ch[0][0]=ch[0][1]=v[0]=s[0]=sum[0]=0; lm[0]=rm[0]=ma[0]=-inf; newnode(root,-inf,0); newnode(ch[root][1],-inf,root); s[root]=2; build(keytree,1,n,ch[root][1]); up(ch[root][1]); up(root);}void rot(int x,int f){ int y=p[x]; p[ch[x][f]]=y; ch[y][!f]=ch[x][f]; p[x]=p[y]; if(p[y]) ch[p[y]][ch[p[y]][1]==y]=x; p[y]=x; ch[x][f]=y; up(y);}void splay(int x,int goal){ while(p[x]!=goal) { if(p[p[x]]==goal)rot(x,ch[p[x]][0]==x); else { int y=p[x],f=ch[p[y]][0]==y; if(ch[y][f]==x) rot(x,!f); else rot(y,f); rot(x,f); } } if(!goal) root=x; up(x);}void rotto(int k,int goal){ int x=root; down(x); while(s[ch[x][0]]!=k) { if(s[ch[x][0]]>k) x=ch[x][0]; else { k-=s[ch[x][0]]+1; x=ch[x][1]; } down(x); } splay(x,goal);}void Same(int pos,int num,int c){ rotto(pos-1,0); rotto(pos+num,root); datasame(keytree, c);}void Rev(int pos,int num){ rotto(pos-1,0); rotto(pos+num,root); datarev(keytree);}void getsum(int pos,int num){ rotto(pos-1,0); rotto(pos+num,root); printf("%d\n",sum[keytree]);}void maxsum(){ rotto(0,0); rotto(s[root]-1,root); printf("%d\n",ma[keytree]);}void eraser(int x){ visit(x);}void insert(int pos,int num){ rotto(pos,0); rotto(pos+1,root); build(keytree,1,num,ch[root][1]); up(ch[root][1]); up(root);}void del(int pos,int num){ rotto(pos-1,0); rotto(pos+num,root); eraser(keytree); keytree=0; up(ch[root][1]); up(root);}int main(){ int i,pos,num,c; char op[20]; while(scanf("%d%d",&n,&m)!=EOF) { for(i=1;i<=n;i++) scanf("%d",&a[i]); init(); while(m--) { scanf("%s",op); switch(op[0]) { case 'I': scanf("%d%d",&pos,&num); for(i=1;i<=num;i++) scanf("%d",&a[i]); insert(pos,num); break; case 'D': scanf("%d%d",&pos,&num);del(pos,num);break; case 'M':if(op[2]=='X') maxsum(); else { scanf("%d%d%d",&pos,&num,&c); Same(pos,num,c); } break; case 'R':scanf("%d%d",&pos,&num);Rev(pos,num);break; case 'G':scanf("%d%d",&pos,&num);getsum(pos,num);break; } } } return 0;}