问题 D: Tyvj 1729 文艺平衡树
题目描述
您需要写一种数据结构（可参考题目标题），来维护一个有序数列，其中需要提供以下操作：翻转一个区间，例如原有序序列是5 4 3 2 1，翻转区间是[2,4]的话，结果是5 2 3 4 1
输入
第一行为n,m n表示初始序列有n个数，这个序列依次是(1,2……n-1,n) m表示翻转操作次数
接下来m行每行两个数[l,r] 数据保证 1<=l<=r<=n
输出
输出一行n个数字，表示原始序列经过m次变换后的结果
样例输入
5 3
1 3
1 3
1 4
样例输出
4 3 2 1 5
提示
啊啊啊Ｏ(≧口≦)Ｏ，我上树啦~~然而我恐高( ⊙ o ⊙ )啊！，好像重回空气清新的地面。。
附两份Splay的代码，一个是指针的，一个是数组的。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 using namespace std; 6 const int N=100010; 7 int n,m,x,y; 8 struct Splay{ 9 int l[N],r[N],k[N],s[N],root; 10 bool tag[N]; 11 int build(int L,int R){ 12 if(L>R) return 0; 13 int mid=(L+R)>>1; 14 s[mid]=R-L+1; 15 l[mid]=build(L,mid-1); 16 r[mid]=build(mid+1,R); 17 return mid; 18 } 19 void pushdown(int x){ 20 if(tag[x]){ 21 swap(l[x],r[x]); 22 tag[l[x]]^=1;tag[r[x]]^=1; 23 tag[x]^=1; 24 } 25 } 26 void update(int x){ 27 s[x]=s[l[x]]+s[r[x]]+1; 28 } 29 void l_rot(int &x){ 30 int y=r[x]; 31 r[x]=l[y];l[y]=x; 32 update(x);update(y); 33 x=y; 34 } 35 void r_rot(int &x){ 36 int y=l[x]; 37 l[x]=r[y];r[y]=x; 38 update(x);update(y); 39 x=y; 40 } 41 void splay(int &x,int k){ 42 pushdown(x); 43 int i=s[l[x]]+1; 44 if(k==i) return; 45 if(k<i) splay(l[x],k),r_rot(x); 46 else splay(r[x],k-i),l_rot(x); 47 48 } 49 void Swap(int L,int R){ 50 splay(root,L); 51 splay(root,R+2); 52 tag[r[l[root]]]^=1; 53 } 54 void search(int x){ 55 if(!x) return; 56 pushdown(x); 57 search(l[x]); 58 if(k[x]) printf("%d ",k[x]); 59 search(r[x]); 60 } 61 }T; 62 inline int read(){ 63 int sum=0;char ch=getchar(); 64 while(ch<'0'||ch>'9') ch=getchar(); 65 while(ch>='0'&&ch<='9'){sum=sum*10+ch-'0';ch=getchar();} 66 return sum; 67 } 68 int main(){ 69 freopen("sph.in","r",stdin); 70 freopen("sph.out","w",stdout); 71 n=read();m=read(); 72 for(int i=1;i<=n;++i) 73 T.k[i+1]=i; 74 T.root=T.build(1,n+2); 75 for(int i=1;i<=m;++i){ 76 x=read();y=read(); 77 T.Swap(x,y); 78 } 79 T.search(T.root); 80 // while(1); 81 return 0; 82 }
这个是数组的。。。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 using namespace std; 6 const int N=100005; 7 int n,m,num,x,y; 8 int read(){ 9 int sum=0,f=1;char ch=getchar(); 10 while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();} 11 while(ch>='0'&&ch<='9') {sum=sum*10+ch-'0';ch=getchar();} 12 return sum*f; 13 } 14 struct Splay{ 15 int num,size;bool tag; 16 Splay *fa,*ch[2]; 17 void pushup(){ 18 size=ch[0]->size+ch[1]->size+1; 19 } 20 bool get(){ 21 return fa->ch[0]==this?0:1; 22 } 23 void set(Splay*,int); 24 }pool[N],*null,*root; 25 void Splay::set(Splay *child,int wh){ 26 ch[wh]=child; 27 if(child!=null) child->fa=this; 28 pushup(); 29 return; 30 } 31 Splay* newnode(int x){ 32 Splay *t=&pool[++num]; 33 t->ch[0]=t->ch[1]=null; 34 t->num=x;t->size=1;t->tag=false; 35 return t; 36 } 37 Splay* build(int l,int r,Splay *now){ 38 if(l>r) return null; 39 int mid=(l+r)>>1; 40 Splay *t=newnode(mid); 41 t->fa=now; 42 t->ch[0]=build(l,mid-1,t); 43 t->ch[1]=build(mid+1,r,t); 44 t->pushup(); 45 return t; 46 } 47 void pushdown(Splay *now){ 48 if(now->tag){ 49 swap(now->ch[0],now->ch[1]); 50 if(now->ch[0]!=null) now->ch[0]->tag^=1; 51 if(now->ch[1]!=null) now->ch[1]->tag^=1; 52 now->tag^=1; 53 } 54 } 55 Splay *kth(int k){ 56 Splay *now=root; 57 while(now!=null){ 58 pushdown(now); 59 if(now->ch[0]->size+1==k) return now; 60 if(now->ch[0]->size+1>k) now=now->ch[0]; 61 else k-=now->ch[0]->size+1,now=now->ch[1]; 62 } 63 return null; 64 } 65 Splay *find(int v){ 66 Splay *now=root; 67 int left=0; 68 while(now!=null){ 69 pushdown(now); 70 int tt=left+now->ch[0]->size; 71 if(v==tt+1) return now; 72 if(tt+1>v) now=now->ch[0]; 73 else left=tt+1,now=now->ch[1]; 74 } 75 } 76 void rotate(Splay *&now){ 77 Splay *pa=now->fa; 78 Splay *ga=pa->fa; 79 if(ga->tag) pushdown(ga); 80 if(pa->tag) pushdown(pa); 81 if(now->tag) pushdown(now); 82 int wz=now->get(); 83 pa->set(now->ch[wz^1],wz);now->set(pa,wz^1); 84 now->fa=ga; 85 if(ga!=null) ga->ch[ga->ch[1]==pa]=now; 86 } 87 void splay(Splay *now,Splay *lim){ 88 for(;now->fa!=lim;rotate(now)) 89 if(now->fa->fa!=lim) 90 now->get()==now->fa->get()?rotate(now->fa):rotate(now); 91 if(lim==null) root=now; 92 } 93 void Swap(int x,int y){ 94 Splay *t=kth(x); 95 splay(t,null); 96 t=kth(y+2); 97 splay(t,root); 98 root->ch[1]->ch[0]->tag^=1; 99 } 100 void search(Splay *now){ 101 if(!now) return; 102 pushdown(now); 103 search(now->ch[0]); 104 if(now!=null&&now->num&&now->num!=n+1) 105 printf("%d ",now->num); 106 search(now->ch[1]); 107 } 108 int main(){ 109 freopen("sph.in","r",stdin); 110 freopen("sph.out","w",stdout); 111 n=read();m=read(); 112 null=newnode(-1); 113 null->size=0; 114 root=newnode((n+1)/2); 115 root->fa=null;int mid=(n+1)>>1; 116 root->ch[0]=build(0,mid-1,root); 117 root->ch[1]=build(mid+1,n+1,root); 118 root->pushup(); 119 for(int i=1;i<=m;++i){ 120 x=read();y=read(); 121 Swap(x,y); 122 } 123 search(root); 124 return 0; 125 }
希望大家一定要学好啊！！！（不要像我）’
N,M<=100000