BZOJ 3223: Tyvj 1729 文艺平衡树-Splay树(区间翻转)模板题

3223: Tyvj 1729 文艺平衡树

Time Limit:10 SecMemory Limit:128 MB

Submit:6881Solved:4213

[Submit][Status][Discuss]

Description

您需要写一种数据结构（可参考题目标题），来维护一个有序数列，其中需要提供以下操作：翻转一个区间，例如原有序序列是54321，翻转区间是[2,4]的话，结果是52341

Input

第一行为n,mn表示初始序列有n个数，这个序列依次是(1,2……n-1,n)m表示翻转操作次数

接下来m行每行两个数[l,r]数据保证1<=l<=r<=n

Output

输出一行n个数字，表示原始序列经过m次变换后的结果

Sample Input

5 3

1 3

1 3

1 4

Sample Output

4 3 2 1 5

HINT

N,M<=100000

模板题，区间翻转问题

延时标记的作用是优化，如果一个区间翻转之后再翻转回来，用延时标记就可以优化，不必再翻转。比如翻转[1,4]，再翻转[1,4]，就可以延时标记优化。

其他的代码里写了注释。

代码:

1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<bitset> 6 #include<cassert> 7 #include<cctype> 8 #include<cmath> 9 #include<cstdlib> 10 #include<ctime> 11 #include<deque> 12 #include<iomanip> 13 #include<list> 14 #include<map> 15 #include<queue> 16 #include<set> 17 #include<stack> 18 #include<vector> 19 using namespace std; 20 typedef long long ll; 21 22 const double PI=acos(-1.0); 23 const double eps=1e-6; 24 const ll mod=1e9+7; 25 const int inf=0x3f3f3f3f; 26 const int maxn=1e5+10; 27 const int maxm=100+10; 28 #define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); 29 30 /* 31 将当前排名为l-1 +1 的节点转到根 32 将当前排名为r+2的节点转到根的右子树的根节点 33 则根的右子树的根节点的左子树为所求区间 34 直接打标记就可以了 35 */ 36 37 int n,m,sz,rt,pre[maxn],l,r,ch[maxn][2],data[maxn],size[maxn],rev[maxn]; 38 39 //在爸爸节点打上标记，然后进行下放，如果进行了两次相反的翻转，lazy标记就会消失，这样就减少了翻转次数达到优化 40 41 void pushup(int k)//要先pushup儿子才能pushup爸爸 42 { 43size[k]=size[ch[k][0]]+size[ch[k][1]]+1;//当前节点的size为左子树+右子树+自己 44 } 45 46 void pushdown(int k)//要先pushdown爸爸才能pushdown儿子 47 { 48int l=ch[k][0],r=ch[k][1];//左儿子和右儿子 49if(rev[k]){//翻转区间 50 swap(ch[k][0],ch[k][1]);//翻转左右儿子 51 rev[l]^=1;rev[r]^=1;//标记下传 52 rev[k]=0;//当前节点标记去掉 53} 54 } 55 56 void rotate(int x,int &k)//翻转操作 57 { 58int y=pre[x],z=pre[y],l,r; 59if(ch[y][0]==x) l=0; 60else l=1; 61r=l^1; 62if(y==k) k=x; 63else{if(ch[z][0]==y) ch[z][0]=x;else ch[z][1]=x;} 64pre[x]=z;pre[y]=x;pre[ch[x][r]]=y; 65ch[y][l]=ch[x][r];ch[x][r]=y; 66pushup(y);pushup(x); 67 } 68 69 void splay(int x,int &k)//splay到目标状态 70 { 71while(x!=k){ 72 int y=pre[x],z=pre[y]; 73 if(y!=k){ 74 if(ch[y][0]==x^ch[z][0]==y)rotate(x,k); 75 else rotate(y,k); 76 } 77 rotate(x,k); 78} 79 } 80 81 int find(int k,int rank) 82 { 83pushdown(k);//有标记就pushdown 84int l=ch[k][0],r=ch[k][1]; 85if(size[l]+1==rank) return k; 86else if(size[l]>=rank) return find(l,rank); 87else return find(r,rank-size[l]-1); 88 } 89 90 void change(int l,int r) 91 { 92int x=find(rt,l),y=find(rt,r+2); 93splay(x,rt);splay(y,ch[x][1]); 94int z=ch[y][0]; 95rev[z]^=1; 96 } 97 98 void build(int l,int r,int f) 99 {100if(l>r) return;101int now=data[l],last=data[f];102if(l==r){103 pre[now]=last;104 size[now]=1;105 if(l<f) ch[last][0]=now;106 else ch[last][1]=now;107 return;108}109 110int mid=(l+r)>>1;111now=data[mid];112build(l,mid-1,mid);113build(mid+1,r,mid);114pre[now]=last;115pushup(mid);116if(mid<f) ch[last][0]=now;117else ch[last][1]=now;118 }119 120 int main()121 {122scanf("%d%d",&n,&m);123for(int i=1;i<=n+2;i++)124 data[i]=++sz;125build(1,n+2,0);//建树，建两个哨兵节点为1，n+2。126rt=(n+3)>>1;//中点为rt127for(int i=1;i<=m;i++){128 scanf("%d%d",&l,&r);129 change(l,r);130}131for(int i=2;i<=n+1;i++)132 printf("%d ",find(rt,i)-1);//去掉哨兵节点133return 0;134 }

先贴个板子，有的操作并不理解，过几天再看。