迷人的伸展樹、、、
都是伸展樹很裸的操作,沒什麼技術含量。
標記下放的時候注意一下就好。。。
#include#include #include #include #include using namespace std; #define LL long long #define maxn 220000 #define mem(a,b) memset(a,b,sizeof(a)) #define root10 ch[ch[root][1]][0] #define root1 ch[root][1] #define root11 ch[ch[root][1]][1] #define lson ch[x][0] #define rson ch[x][1] #define INF ~0u>>2 int ch[maxn][2]; int pre[maxn]; int root,tot; int size[maxn]; int val[maxn]; int rev[maxn]; int lazy[maxn]; int minn[maxn]; //---------------------- int num[maxn]; int st[maxn]; void Treaval(int x) { if(x) { Treaval(ch[x][0]); printf("結點%2d:左兒子 %2d 右兒子 %2d 父結點 %2d size = %2d ,key = %2d\n",x,ch[x][0],ch[x][1],pre[x],size[x],val[x]); Treaval(ch[x][1]); } } void debug() { printf("root:%d\n",root); Treaval(root); } void debug2() { puts("start:"); for(int x=1;x<=tot;x++) { printf("結點%2d:左兒子 %2d 右兒子 %2d 父結點 %2d size = %2d ,key = %2d \n",x,ch[x][0],ch[x][1],pre[x],size[x],val[x]); } } //以上Debug void push_down(int x) { if(lazy[x]) { if(lson) { lazy[lson]+=lazy[x]; val[lson]+=lazy[x]; minn[lson]+=lazy[x]; } if(rson) { lazy[rson]+=lazy[x]; val[rson]+=lazy[x]; minn[rson]+=lazy[x]; } lazy[x]=0; } if(rev[x]) { rev[lson]^=1; rev[rson]^=1; swap(lson,rson); rev[x]=0; } } void push_up(int x) { size[x]=size[lson]+size[rson]+1; minn[x]=val[x]; if(lson)minn[x]=min(minn[x],minn[lson]); if(rson)minn[x]=min(minn[x],minn[rson]); } void rot(int x,int kind) { int y=pre[x]; push_down(y); push_down(x); ch[y][!kind]=ch[x][kind]; pre[ch[x][kind]]=y; if(pre[y])ch[pre[y]][ch[pre[y]][1]==y]=x; pre[x]=pre[y]; ch[x][kind]=y; pre[y]=x; push_up(y); push_up(x); } void splay(int x,int goal) { push_down(x); while(pre[x]!=goal) { if(pre[pre[x]]==goal) { push_down(pre[x]); push_down(x); rot(x,ch[pre[x]][0]==x); } else { int y=pre[x]; push_down(pre[y]); push_down(y); push_down(x); int kind=ch[pre[y]][0]==y; if(ch[y][kind]==x) { rot(x,!kind); rot(x,kind); } else { rot(y,kind); rot(x,kind); } } } push_up(x); if(goal==0)root=x; } void init() { root=tot=0; size[0]=0; memset(ch,0,sizeof(ch)); memset(pre,0,sizeof(pre)); } void newnode(int &x,int k,int father) { x=++tot; pre[x]=father; size[x]=1; ch[x][0]=ch[x][1]=0; val[x]=k; rev[x]=lazy[x]=0; minn[x]=k; // printf("val[%d]=%d,st[%d]=%d\n",x,k,k,x); } void buildtree(int &x,int l,int r,int father) { if(l>r)return; int mid=(l+r)/2; newnode(x,num[mid],father); buildtree(ch[x][0],l,mid-1,x); buildtree(ch[x][1],mid+1,r,x); push_up(x); } int get_kth(int x,int k) { push_down(x); int p=size[ch[x][0]]; if(p+1==k)return x; else if(k<=p)return get_kth(ch[x][0],k); else get_kth(ch[x][1],k-p-1); } int get_max(int r) { push_down(r); while(ch[r][1]) { r=ch[r][1]; push_down(r); } return r; } int get_min(int r) { push_down(r); while(ch[r][0]) { r=ch[r][0]; push_down(r); } return r; } int main() { int n,x; int cas=0; int q,a,b,c; while(~scanf("%d",&n)) { for(int i=1;i<=n;i++) { scanf("%d",&num[i]); } init(); newnode(root,INF,0); newnode(root1,INF,root); size[root]=2; buildtree(root10,1,n,root1); push_up(root1);push_up(root); scanf("%d",&q); char str[110]; //cout< b)swap(a,b); int x=get_kth(root,a); int y=get_kth(root,b+2); splay(x,0); splay(y,root); lazy[root10]+=c; val[root10]+=c; minn[root10]+=c; } else if(str[0]=='R'&&str[3]=='E') { scanf("%d%d",&a,&b); if(a>b)swap(a,b); int x=get_kth(root,a); int y=get_kth(root,b+2); splay(x,0); splay(y,root); rev[root10]^=1; } else if(str[0]=='R'&&str[3]=='O') { scanf("%d%d%d",&a,&b,&c); if(a>b)swap(a,b); int m=b-a+1; c=c%m;c=(c+m)%m; if(c==0)continue; int x=get_kth(root,a); int y=get_kth(root,a+1); int xx=get_kth(root,b-c+1); int yy=get_kth(root,b+2); splay(xx,0); splay(yy,root); int ps=root10; root10=0; push_up(root1);push_up(root); splay(x,0); splay(y,root); root10=ps; pre[ps]=root1; push_up(root1);push_up(root); } else if(str[0]=='I') { scanf("%d%d",&a,&b); int x=get_kth(root,a+1); int y=get_kth(root,a+2); splay(x,0); splay(y,root); newnode(root10,b,root1); push_up(root1);push_up(root); } else if(str[0]=='D') { scanf("%d",&a); int x=get_kth(root,a); int y=get_kth(root,a+2); splay(x,0); splay(y,root); root10=0; push_up(root1); push_up(root); } else if(str[0]=='M') { scanf("%d%d",&a,&b); if(a>b)swap(a,b); int x=get_kth(root,a); int y=get_kth(root,b+2); splay(x,0); splay(y,root); printf("%d\n",minn[root10]); } } } return 0; }