題目大意

給出一個序列，要求你支持區間反轉，交換相鄰區間，添加一個元素和刪除一個元素，以及查詢區間最小值等操作。

序列之王——splay

對于區間反轉，可以類似懶標記傳遞修改。
添加或刪除一個元素都可以通過splay操作使要添加或刪除的元素成為葉子節點，然后就很容易添加或修改了
交換相鄰區間，相對比較麻煩。
有一個機智的做法，利用反轉來實現，
假如我們要交換[a,b]和[b+1,c]兩個區間，其實也就相當于三個反轉操作，先反轉[a,b]和[b+1,c]，再反轉[a,c]。

代碼

(作為蒟蒻我調試了一個白天)

#include<cstring> #include<algorithm> #include<cmath> #include<cstdio> #define fo(i,a,b) for(i=a;i<=b;i++) #define fod(i,a,b) for(i=a;i>=b;i--) using namespace std; const int maxn=200000+5; int i,j,n,m,root; int a[maxn],tree[maxn][2],num[maxn],bz[maxn],bf[maxn],fa[maxn],q[maxn],s[maxn],cnt; void update(int x){num[x]=min(a[x],min(num[tree[x][0]],num[tree[x][1]]));s[x]=s[tree[x][0]]+s[tree[x][1]]+1; } int pd(int x){if (tree[fa[x]][0]==x) return 0;return 1; } void rotate(int x){int y=fa[x],z=pd(x),z1=pd(y);tree[y][z]=tree[x][1-z];if (tree[x][1-z]) fa[tree[x][1-z]]=y;if (fa[y]) tree[fa[y]][z1]=x;fa[x]=fa[y];tree[x][1-z]=y;fa[y]=x;update(y); } void ch(int x,int y){if (x==0) return;a[x]+=y;num[x]+=y;bz[x]+=y; } void clear(int x){if (bz[x]){ch(tree[x][0],bz[x]);ch(tree[x][1],bz[x]); } if (bf[x]){bf[x]=0;int l=tree[x][0],r=tree[x][1];if (l)bf[l]=!bf[l];if (r)bf[r]=!bf[r];swap(tree[x][0],tree[x][1]);}bf[x]=bz[x]=0; } void chu(int x,int y){q[0]=0;while (x!=y){q[++q[0]]=x;x=fa[x];}int i;fod(i,q[0],1) clear(q[i]); } void splay(int x,int y){chu(x,y);while (fa[x]!=y){int f=fa[x];if (fa[f]!=y)if (pd(f)==pd(x)) rotate(f);else rotate(x);rotate(x);}update(x);if (!y) root=x; } int kth(int x,int k){clear(x); if (s[tree[x][0]]+1==k) return x;if (s[tree[x][0]]+1>k) return kth(tree[x][0],k);elsereturn kth(tree[x][1],k-s[tree[x][0]]-1); } void fan(int x,int y){if (x==y) return;x=kth(root,x);y=kth(root,y+2);splay(x,0);splay(y,x);bf[tree[y][0]]=!bf[tree[y][0]]; } void ins(int x,int y){int w=kth(root,x+1),b=kth(root,x+2);splay(w,0);splay(b,w);tree[b][0]=++cnt;fa[cnt]=b;num[cnt]=a[cnt]=y;s[cnt]=1;update(b);update(w); } void del(int x){int w=kth(root,x),b=kth(root,x+2);splay(w,0);splay(b,w);tree[b][0]=0;update(b);update(w); } int main(){while (~scanf("%d",&n)){a[0]=a[n+1]=a[n+2]=num[0]=num[n+1]=num[n+2]=maxn*1000;memset(tree,0,sizeof(tree));s[n+1]=s[n+2]=1;fo(i,1,n) {scanf("%d",&a[i]);if (i>1) tree[i][0]=i-1,fa[i-1]=i;else tree[1][0]=n+1,fa[n+1]=1;update(i);}tree[n+2][0]=n,fa[n]=n+2;update(n+2);cnt=n+2;splay(1,0);root=1;scanf("%d",&m);fo(i,1,m){int x,y,t,d;char c;c=getchar();while ((c<'A')||(c>'Z')) c=getchar();if (c=='A') {t=1;fo(j,1,2) c=getchar();}else if (c=='R'){fo(j,1,6) {c=getchar();if (j==3)if (c=='E') t=2;else t=3;}}else if (c=='I'){t=4;fo(j,1,5) c=getchar();}else if (c=='D'){t=5;fo(j,1,5) c=getchar();}else {t=6;fo(j,1,2) c=getchar();}if (t==1){scanf("%d%d%d",&x,&y,&d);x=kth(root,x);y=kth(root,y+2);splay(x,0);splay(y,x);ch(tree[y][0],d);update(y);update(x);}if (t==2){scanf("%d%d",&x,&y);fan(x,y);}if (t==3){scanf("%d%d%d",&x,&y,&d);int l=y-x+1;d=(d%l+l)%l;if (d) fan(x,y-d),fan(y-d+1,y),fan(x,y);}if (t==4){scanf("%d%d",&x,&y);ins(x,y);}if (t==5){scanf("%d",&x);del(x);}if (t==6){scanf("%d%d",&x,&y);x=kth(root,x);y=kth(root,y+2);splay(x,0);splay(y,x);printf("%d\n",num[tree[y][0]]);}} } }

總結

以上是生活随笔為你收集整理的SuperMemo的全部內容，希望文章能夠幫你解決所遇到的問題。

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