区间操作的究极题，我们一个个来分析
其实只有insert,delete,revolve三种没讲过
insert 先把x旋到根，一开始我比较SB的，准备把新节点插入到右子树的最左节点，这显然很烦
好的方法是，直接在根和右孩子之间插入即可，相当于right[new]=right[root] right[root]=new
然后维护一下new和root即可即可
delete 我一开始使用的是杨思雨大神splay论文中的方法，但是好像很烦
后来发现，一个比较简洁的做法，先把x的后继旋到根，然后把x旋到根的儿子的位置上（显然是左孩子）
显然x是不含有右子树的，所以，直接删去x即可（就是x的左子树直接与根相连
revolve 这是这道题最难的一个操作了，感觉自己写的也不是很好，还是讲讲方法吧
首先这个操作的本质是[l,k][k+1,r]这两个区间交换位置
考虑到假如在k和k+1中间有一个中间点，那么我只要把中间点旋到区间的根上然后直接交换左右子树即可
但是是不存在的，所以我们考虑先把k作为这个中间点，交换完左右子树后再把k插入到区间最后
也就是先把k旋到区间根上，然后交换左右子树，然后把k节点删去，再把他插入区间末尾
如果l=k，就不需要删去插入这一步了，感觉写得挺麻烦的
1 const inf=2147483647; 2 3 var son:array[0..200010,1..2] of longint; 4 count,fa,a,lazy,mina:array[0..200010] of longint; 5 v:array[0..200010] of boolean; 6 n,m,i,x,y,z,p,root:longint; 7 s:string; 8 ch:char; 9 10 function min(a,b:longint):longint; 11 begin 12 if a>b then exit(b) else exit(a); 13 end; 14 15 procedure swap(var a,b:longint); 16 var c:longint; 17 begin 18 c:=a; 19 a:=b; 20 b:=c; 21 end; 22 23 procedure add(x,y:longint); 24 begin 25 mina[x]:=mina[x]+y; 26 a[x]:=a[x]+y; 27 lazy[x]:=lazy[x]+y; 28 end; 29 30 procedure change(x:longint); 31 begin 32 swap(son[x,1],son[x,2]); 33 v[x]:=not v[x]; 34 end; 35 36 procedure update(x:longint); 37 begin 38 count[x]:=count[son[x,1]]+count[son[x,2]]+1; 39 mina[x]:=min(a[x],min(mina[son[x,1]],mina[son[x,2]])); 40 end; 41 42 procedure push(x:longint); 43 var l,r:longint; 44 begin 45 l:=son[x,1]; 46 r:=son[x,2]; 47 if lazy[x]<>0 then 48 begin 49 if l<>-1 then add(l,lazy[x]); 50 if r<>-1 then add(r,lazy[x]); 51 lazy[x]:=0; 52 end; 53 if v[x] then 54 begin 55 if l<>-1 then change(l); 56 if r<>-1 then change(r); 57 v[x]:=false; 58 end; 59 end; 60 61 procedure rotate(x,w:longint); 62 var y:longint; 63 begin 64 push(x); 65 y:=fa[x]; 66 if fa[y]<>-1 then 67 begin 68 if son[fa[y],1]=y then son[fa[y],1]:=x 69 else son[fa[y],2]:=x; 70 end 71 else root:=x; 72 fa[x]:=fa[y]; 73 son[y,3-w]:=son[x,w]; 74 if son[x,w]<>-1 then fa[son[x,w]]:=y; 75 son[x,w]:=y; 76 fa[y]:=x; 77 update(y); 78 update(x); 79 end; 80 81 procedure splay(x,f:longint); 82 var y:longint; 83 begin 84 while fa[x]<>f do 85 begin 86 y:=fa[x]; 87 if fa[y]=f then 88 begin 89 if son[y,1]=x then rotate(x,2) 90 else rotate(x,1); 91 end 92 else begin 93 if son[fa[y],1]=y then 94 begin 95 if son[y,1]=x then rotate(y,2) else rotate(x,1); 96 rotate(x,2); 97 end 98 else begin 99 if son[y,1]=x then rotate(x,2) else rotate(y,1); 100 rotate(x,1); 101 end; 102 end; 103 end; 104 end; 105 106 function find(k:longint):longint; 107 var p:longint; 108 begin 109 p:=root; 110 while true do 111 begin 112 push(p); 113 if count[son[p,1]]+1=k then exit(p); 114 if count[son[p,1]]+1>k then p:=son[p,1] 115 else begin 116 k:=k-count[son[p,1]]-1; 117 p:=son[p,2]; 118 end; 119 end; 120 end; 121 122 procedure getrange; //提取区间 123 begin 124 x:=find(x); 125 y:=find(y+2); 126 splay(x,-1); 127 splay(y,x); 128 end; 129 130 procedure insert(x,p:longint); // p是新插入节点 131 begin 132 splay(x,-1); 133 son[p,2]:=son[x,2]; 134 fa[son[x,2]]:=p; 135 son[x,2]:=p; 136 fa[p]:=x; 137 update(p); 138 update(x); 139 end; 140 141 procedure delete(x,p:longint); //p是x的后继节点 142 begin 143 splay(p,-1); 144 splay(x,p); 145 if son[x,1]<>-1 then fa[son[x,1]]:=p; 146 son[p,1]:=son[x,1]; 147 son[x,1]:=-1; 148 son[x,2]:=-1; 149 fa[x]:=-1; 150 update(p); 151 end; 152 153 function build(l,r:longint):longint; 154 var m:longint; 155 begin 156 m:=(l+r) shr 1; 157 build:=m; 158 if m-1>=l then 159 begin 160 son[m,1]:=build(l,m-1); 161 fa[son[m,1]]:=m; 162 end; 163 if m+1<=r then 164 begin 165 son[m,2]:=build(m+1,r); 166 fa[son[m,2]]:=m; 167 end; 168 update(m); 169 end; 170 171 procedure revolve; 172 var l,r,p,last:longint; 173 begin 174 last:=find(y-z+1); // 交换[x,y-z][y-z+1,y]; 175 if y-z=x then 176 begin 177 getrange; 178 splay(last,y); 179 swap(son[last,1],son[last,2]); 180 end 181 else begin 182 l:=x; 183 r:=y; 184 getrange; 185 splay(last,y); 186 swap(son[last,1],son[last,2]); 187 //交换完后，中间点对应区间上的点也不同了 188 p:=find(l+z+2); //注意这里两处找位置对应树上的点，交换删除后，同一位置对应树上的点会不不同 189 delete(last,p); 190 p:=find(r); 191 insert(p,last); 192 end; 193 end; 194 195 begin 196 readln(n); 197 fillchar(son,sizeof(son),255); 198 fillchar(fa,sizeof(fa),255); 199 for i:=1 to n do 200 readln(a[i]); 201 for i:=-1 to n+1 do 202 mina[i]:=inf; 203 count[-1]:=0; 204 a[-1]:=inf; 205 a[0]:=inf; 206 a[n+1]:=inf; 207 root:=build(0,n+1); 208 inc(n); 209 readln(m); 210 for i:=1 to m do 211 begin 212 read(ch); 213 s:=''; 214 while ch<>' ' do 215 begin 216 s:=s+ch; 217 read(ch); 218 end; 219 if s='ADD' then 220 begin 221 readln(x,y,z); 222 getrange; 223 add(son[y,1],z); 224 end 225 else if s='REVERSE' then 226 begin 227 readln(x,y); 228 getrange; 229 change(son[y,1]); 230 end 231 else if s='REVOLVE' then 232 begin 233 readln(x,y,z); 234 z:=z mod (y-x+1); //注意 235 if z<>0 then revolve; 236 end 237 else if s='INSERT' then 238 begin 239 readln(x,y); 240 x:=find(x+1); 241 inc(n); mina[n]:=y; a[n]:=y; count[n]:=1; 242 insert(x,n); 243 end 244 else if s='DELETE' then 245 begin 246 readln(x); 247 p:=find(x+2); 248 x:=find(x+1); 249 delete(x,p); 250 end 251 else begin 252 readln(x,y); 253 getrange; 254 writeln(mina[son[y,1]]); 255 end; 256 end; 257 end.