splay2(区间修改+内存回收)

void small_const_rotate(int x,int d){
  int y=T[x].fa;
  T[y].son[!d]=T[x].son[d];
  T[T[x].son[d]].fa=y;
  if(T[y].fa) T[T[y].fa].son[T[T[y].fa].son[1]==y]=x;
  T[x].fa=T[y].fa,T[x].son[d]=y;
  T[y].fa=x;
  up(y);
}

void small_const_splay(int x,int goal){//伸展操作，将x调整到goal下面
  lazy(x);
  while(T[x].fa!=goal){
    if(T[T[x].fa].fa==goal){
      lazy(T[x].fa),lazy(x);
      rotate(x,T[T[x].fa].son[0]==x);//这题有反转操作，需要先lazy,在判断左右孩子
    }
    else{
      lazy(T[T[x].fa].fa),lazy(T[x].fa),lazy(x);//这题有反转操作，需要先lazy,在判断左右孩子
      int y=T[x].fa , k=(T[T[y].fa].son[0]==y);
      if(T[y].son[k]==x)rotate(x,k^1),rotate(x,k);//两个方向不同，则先左旋再右旋
      else              rotate(y,k),rotate(x,k);  //两个方向相同，相同方向连续两次
    }
  }
  up(x);
  if(goal==0) root=x;
}

  1 #include <algorithm>
  2 #include <iostream>
  3 #include <cstring>
  4 #include <cstdlib>
  5 #include <cstdio>
  6 #include <vector>
  7 #include <cmath>
  8 #include <queue>
  9 #include <map>
 10 #include <set>
 11 using namespace std;
 12 #define file(x) freopen(x".in","r",stdin),freopen(x".out","w",stdout)
 13 #define Front T[T[root].son[1]].son[0]
 14 #define ls T[x].son[0]
 15 #define rs T[x].son[1]
 16 const int MAXN=100000+10;
 17 const int INF=(int)2e9;
 18 int a[MAXN],n,m;
 19 struct splay_tree{
 20   struct Node{
 21     int son[2],fa,key,size,add,rev,min;
 22     void init(){
 23       son[0]=son[1]=fa=key=size=add=rev=0;
 24       min=INF;
 25     }
 26   }T[MAXN];
 27   int root,tot,s[MAXN],top;//内存池、内存池容量
 28 
 29   void NewNode(int &x,int fa,int key){
 30     if(top)x=s[top--];
 31     else    x=++tot;
 32     ls=rs=0;
 33     T[x].fa=fa,T[x].size=1;
 34     T[x].add=T[x].rev=0;
 35     T[x].key=T[x].min=key;
 36   }
 37 
 38   void up_rev(int x){
 39     if(x==0)return;
 40     swap(ls,rs); T[x].rev^=1;
 41   }
 42 
 43   void up_add(int x,int val){
 44     if(x==0)return;
 45     T[x].add+=val; T[x].key+=val; T[x].min+=val;
 46   }
 47 
 48   void up(int x){
 49     T[x].size=T[ls].size+T[rs].size+1;
 50     T[x].min=T[x].key;
 51     if(ls)T[x].min=min(T[x].min,T[ls].min);
 52     if(rs)T[x].min=min(T[x].min,T[rs].min);
 53   }
 54 
 55   void lazy(int x){
 56     if(T[x].rev){
 57       up_rev(ls); up_rev(rs);
 58       T[x].rev=0;
 59     }
 60     if(T[x].add){
 61       up_add(ls,T[x].add); 
 62       up_add(rs,T[x].add);
 63       T[x].add=0;
 64     }
 65   }
 66 
 67   void build(int &x,int l,int r,int fa){
 68     if(l>r)return;
 69     int mid=(l+r)>>1;
 70     NewNode(x,fa,a[mid]);
 71     build(ls,l,mid-1,x);
 72     build(rs,mid+1,r,x);
 73     up(x);
 74   }
 75 
 76   void init(){
 77     root=tot=top=0;
 78     T[root].init();
 79     NewNode(root,0,INF);
 80     NewNode(T[root].son[1],root,INF);
 81     build(Front,1,n,T[root].son[1]);
 82     up(T[root].son[1]);
 83     up(root);
 84   }
 85 
 86   void rotate(int x,int k){
 87     int y=T[x].fa,z=T[y].fa;
 88     T[y].son[k^1]=T[x].son[k] ,T[T[x].son[k]].fa=y;
 89     T[x].son[k]=y ,T[y].fa=x;
 90     T[z].son[T[z].son[1]==y]=x ,T[x].fa=z;
 91     up(y);
 92   }
 93 
 94   void splay(int x,int goal){
 95     if(x==goal)return;
 96     while(T[x].fa!=goal){
 97       int y=T[x].fa ,z=T[y].fa;
 98       lazy(z) ,lazy(y) ,lazy(x);
 99       int rx=T[y].son[0]==x ,ry=T[z].son[0]==y;
100       if(z==goal)rotate(x,rx);
101       else{
102     if(rx==ry)rotate(y,ry);
103     else      rotate(x,rx);
104     rotate(x,ry);
105       }
106     }
107     up(x);
108     if(goal==0)root=x;
109   }
110 
111   int kth(int r,int k){
112     lazy(r);
113     int t=T[T[r].son[0]].size+1;
114     if(t==k)return r;
115     if(t>k) return kth(T[r].son[0],k);
116     else    return kth(T[r].son[1],k-t);
117   }
118 
119   void erase(int x){
120     if(x){
121       s[++top]=x;
122       erase(T[x].son[0]);
123       erase(T[x].son[1]);
124     }
125   }
126 
127   void update_add(int l,int r,int val){
128     splay(kth(root,l),0);
129     splay(kth(root,r+2),root);
130     up_add(Front,val);
131     up(T[root].son[1]);
132     up(root);
133   }
134 
135   void update_reverse(int l,int r){
136     splay(kth(root,l),0);
137     splay(kth(root,r+2),root);
138     up_rev(Front);
139     up(T[root].son[1]);
140     up(root);
141   }
142 
143   void update_revolve(int l,int r,int t){
144     int len=r-l+1; t=(t%len+len)%len;if(t==0) return;
145     int k=r-t+1;
146     splay(kth(root,k),0);
147     splay(kth(root,r+2),root);
148     int tmp=Front;
149     Front=0;
150     up(T[root].son[1]);
151     up(root);
152     splay(kth(root,l),0);
153     splay(kth(root,l+1),root);
154     Front=tmp;
155     T[Front].fa=T[root].son[1];
156     up(T[root].son[1]);
157     up(root);
158   }
159 
160   void update_insert(int x,int P){
161     splay(kth(root,x+1),0);
162     splay(kth(root,x+2),root);
163     NewNode(Front,T[root].son[1],P);
164     up(T[root].son[1]);
165     up(root);
166   }
167 
168   void update_delete(int x){
169     splay(kth(root,x),0);
170     splay(kth(root,x+2),root);
171     erase(Front);
172     T[Front].fa=0;
173     Front=0;
174     up(T[root].son[1]);
175     up(root);
176   }
177 
178   int query_min(int l,int r){
179     splay(kth(root,l),0);
180     splay(kth(root,r+2),root);
181     return T[Front].min;
182   }
183 
184   void work(){
185     char str[10];int x,y,D,P,T;
186     scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d",&a[i]);
187     init();
188     for(scanf("%d",&m);m--;){
189       scanf("%s%d",str,&x);
190       if(strcmp(str,"ADD")==0)scanf("%d%d",&y,&D),update_add(x,y,D);
191       else if(strcmp(str,"REVERSE")==0)scanf("%d",&y),update_reverse(x,y);
192       else if(strcmp(str,"REVOLVE")==0)scanf("%d%d",&y,&T),update_revolve(x,y,T);
193       else if(strcmp(str,"INSERT")==0)scanf("%d",&P),update_insert(x,P);
194       else if(strcmp(str,"DELETE")==0)update_delete(x);
195       else if(strcmp(str,"MIN")==0)scanf("%d",&y),printf("%d\n",query_min(x,y));
196     }
197   }
198 
199 }poj3580;
200 int main(){poj3580.work();return 0;}