傳送門

---

題意：
你需要維護一組數字，包括這樣的幾個操作：
給出一個數字序列，有6種操作：
1、 ADD l r d：區間[l,r]的數都加上d。
2、 REVERSE l r ： 將區間[l,r]中的數翻轉 。
3、 REVOLVE l r t ：將區間[l,r]旋轉t次，如1 2 3 4 5 旋轉2次后就變成4 5 1 2 3 。
4、 INSERT p x ：在第p個數后面插入x 。
5、DELETE p ：刪除第p個數 。
6、 MIN l r ： 查詢區間[x,y]中的最小值 。

---

一道不錯的splay練手題。
首先用類似線段樹的中序遍歷建樹保證二叉搜索樹性質。

對于所有的區間[l,r]操作，可以把l-1旋轉到根，r+1旋轉到l-1的下面，那么由于二叉搜索樹的性質，這時候r+1的左子樹就是[l,r]區間。

那么對于區間加法，我們需要維護一個lazy的加法標記，在旋轉的時候Pushdown傳遞標記給左右孩子（與線段樹相同），對于區間翻轉，由于二叉搜索樹的性質，我們在翻轉某一棵樹的時候只要把他所有的子樹的左右孩子翻轉一下就好了，那么一樣維護一個lazy的旋轉標記即可。

對于在p后插入x，我們模仿區間操作的方法，把p和p+1之間的空間“撐”開來。也就是說把p翻轉到根，把p+1旋轉到p的下面，那么p+1的左子樹就空出來了，就可以將新節點插入進去。

對于刪除p，我們同樣把p-1旋轉到根，把p+1旋轉到p-1的下面，那么p+1的左子樹就是p，直接刪掉即可，空間蠻大的這時候最好回收空間。

區間最小值很簡單，我們維護一個最小值mn，在Pushup的時候和子樹大小size一起被左右孩子更新即可。

接下來剩下的操作就是這題的特殊操作，區間旋轉，我們不難發現，因為旋轉[l,r]區間t次是往后面推t個數然后放到前面，所以區旋轉實際上是交換兩個區間。那么我們把旋轉[l,r]區間t次可以看做交換[l,r-t]和[r-t+1,r]，具體的操作也是區間操作，先把后面被推出去的那段拿出來，放到前面即可。

注意，對于任何涉及區間操作的題目都要設置哨兵節點。

---

#include<cstdio> #include<iostream> #include<cstring> #include<algorithm> #include<cmath> using namespace std; typedef long long ll; const int N=1e5+10; const int INF=2147483647; inline int read() {int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f; }struct splay {int d,f,size,son[2];int fz,mn,add; }tr[N*2]; int tot,root,n; void newnode(int x,int d,int f)//新建節點，東西比較多就單放出來了 {tr[x].f=f; tr[x].d=tr[x].mn=d;tr[x].size=1; tr[x].fz=tr[x].add=0;tr[x].son[0]=tr[x].son[1]=0; } void delnode(int x)//刪除節點 {tr[x].f=tr[x].d=tr[x].size=tr[x].mn=0;tr[x].son[0]=tr[x].son[1]=tr[x].fz=tr[x].add=0; } void update_add(int x,int d)//執行加 {if(!x) return ;tr[x].add+=d; tr[x].d+=d; tr[x].mn+=d; } void update_fz(int x)//執行翻轉 {if(!x) return;swap(tr[x].son[0],tr[x].son[1]);tr[x].fz^=1; } void pushup(int x)//向上更新size,min {if(!x) return ;int lc=tr[x].son[0],rc=tr[x].son[1];tr[x].size=1; tr[x].mn=tr[x].d;if(lc) tr[x].size+=tr[lc].size,tr[x].mn=min(tr[x].mn,tr[lc].mn);if(rc) tr[x].size+=tr[rc].size,tr[x].mn=min(tr[x].mn,tr[rc].mn); } void pushdown(int x)//lazy:更新下方add,fz {if(!x) return;if(tr[x].add){update_add(tr[x].son[0],tr[x].add);update_add(tr[x].son[1],tr[x].add);tr[x].add=0;}if(tr[x].fz){update_fz(tr[x].son[0]);update_fz(tr[x].son[1]);tr[x].fz=0; } } void rotate(int x,int w) {int f=tr[x].f,ff=tr[f].f;int r,R;pushdown(f); pushdown(x);r=tr[x].son[w],R=f;tr[R].son[1-w]=r;if(r!=0) tr[r].f=R;r=x,R=ff;if(tr[ff].son[0]==f) tr[R].son[0]=r;else tr[R].son[1]=r;tr[r].f=R;r=f,R=x;tr[R].son[w]=r;tr[r].f=R;pushup(f);pushup(x); }void splay(int x,int rt) {pushdown(x);while(tr[x].f!=rt){int f=tr[x].f,ff=tr[f].f;pushdown(ff),pushdown(f),pushdown(x);if(ff==rt){if(tr[f].son[0]==x) rotate(x,1);else rotate(x,0);}else {if(tr[ff].son[0]==f && tr[f].son[0]==x) rotate(f,1),rotate(x,1);else if(tr[ff].son[1]==f && tr[f].son[1]==x) rotate(f,0),rotate(x,0);else if(tr[ff].son[0]==f && tr[f].son[1]==x) rotate(x,0),rotate(x,1);else if(tr[ff].son[1]==f && tr[f].son[0]==x) rotate(x,1),rotate(x,0);//三點一線的情況不能單旋否則復雜度退化 }}pushup(x);if(rt==0) root=x; } int a[N]; void build(int &x,int l,int r,int f) { //中序遍歷建樹保證平衡 if(l>r) return;int mid=(l+r)/2;x=mid; newnode(x,a[x],f);build(tr[x].son[0],l,mid-1,x);build(tr[x].son[1],mid+1,r,x);pushup(x); }int find_kth(int x,int k) {pushdown(x);if(tr[tr[x].son[0]].size+1 == k) return x;else if(tr[tr[x].son[0]].size >= k) return find_kth(tr[x].son[0],k);else return find_kth(tr[x].son[1], k-tr[tr[x].son[0]].size-1); }//--------- void add(int l,int r,int d) //[l~r]加d {int x=find_kth(root,l-1),y=find_kth(root,r+1);splay(x,0); splay(y,x);update_add(tr[y].son[0],d); } void ins(int p,int x)//p后面插入x {int y=find_kth(root,p),z=find_kth(root,p+1);splay(y,0); splay(z,y);newnode(++tot,x,z); tr[z].son[0]=tot;for(int i=z;i;i=tr[i].f) pushdown(i),pushup(i);splay(z,0); } void del(int p)//刪除p {int x=find_kth(root,p-1),y=find_kth(root,p+1);splay(x,0); splay(y,x);delnode(tr[y].son[0]); tr[y].son[0]=0;pushup(y); pushup(x); } int get_min(int l,int r)//[l,r]間最小值 {int x=find_kth(root,l-1),y=find_kth(root,r+1);splay(x,0); splay(y,x);return tr[tr[y].son[0]].mn; } void rev(int l,int r)//翻轉[l,r] {int x=find_kth(root,l-1),y=find_kth(root,r+1);splay(x,0); splay(y,x);update_fz(tr[y].son[0]); } void exchange(int l1,int r1,int l2,int r2)//區間[l1,r1],[l2,r2]交換 {int x=find_kth(root,l2-1),y=find_kth(root,r2+1);splay(x,0); splay(y,x); //導出區間int tmp=tr[y].son[0]; tr[y].son[0]=0; //剪貼 x=find_kth(root,l1-1),y=find_kth(root,l1);splay(x,0); splay(y,x);tr[y].son[0]=tmp;tr[tmp].f=y; } //---char ss[10]; int main() {scanf("%d",&n);a[1]=a[n+1]=INF;//設立哨兵節點 for(int i=2;i<=n+1;i++) scanf("%d",&a[i]);tot=n+2; root=0;tr[0].f=tr[0].size=tr[0].son[0]=tr[0].son[1]=tr[0].add=tr[0].fz=0; tr[0].d=INF; build(root,1,n+2,0);pushup(root);int m;scanf("%d",&m);int l,r,d; while(m--)//由于有哨兵節點后面的位置都要+1 {scanf("%s",ss);if(ss[0]=='A'){l=read(),r=read(),d=read();add(l+1,r+1,d);}else if(ss[0]=='I'){l=read(),d=read();ins(l+1,d); }else if(ss[0]=='D'){d=read();del(d+1); }else if(ss[0]=='M'){l=read(),r=read();printf("%d\n",get_min(l+1,r+1)); }else if(ss[0]=='R' && ss[3]=='E'){l=read(),r=read();rev(l+1,r+1); }else if(ss[0]=='R' && ss[3]=='O'){l=read(),r=read(),d=read();d%=(r-l+1);if(d) exchange(l+1,r-d+1,r-d+1+1,r+1); }}return 0; }

總結

以上是生活随笔為你收集整理的[poj3580]SuperMemo（splay终结题）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。