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

3223: Tyvj 1729 文艺平衡树

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 6881  Solved: 4213
[Submit][Status][Discuss]

Description

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

Input

第一行为n,m n表示初始序列有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]，就可以延时标记优化。

其他的代码里写了注释。

代码:

 #include<iostream>
 #include<cstdio>
 #include<cstring>
 #include<algorithm>
 #include<bitset>
 #include<cassert>
 #include<cctype>
 #include<cmath>
 #include<cstdlib>
 #include<ctime>
 #include<deque>
 #include<iomanip>
 #include<list>
 #include<map>
 #include<queue>
 #include<set>
 #include<stack>
 #include<vector>
 using namespace std;
 typedef long long ll;

 const double PI=acos(-1.0);
 const double eps=1e-;
 const ll mod=1e9+;
 const int inf=0x3f3f3f3f;
 const int maxn=1e5+;
 const int maxm=+;
 #define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

 /*
 将当前排名为l-1 +1 的节点转到根
 将当前排名为r+2的节点转到根的右子树的根节点
 则根的右子树的根节点的左子树为所求区间
 直接打标记就可以了
 */

 int n,m,sz,rt,pre[maxn],l,r,ch[maxn][],data[maxn],size[maxn],rev[maxn];

 //在爸爸节点打上标记，然后进行下放，如果进行了两次相反的翻转，lazy标记就会消失，这样就减少了翻转次数达到优化

 void pushup(int k)//要先pushup儿子才能pushup爸爸
 {
     size[k]=size[ch[k][]]+size[ch[k][]]+;//当前节点的size为左子树+右子树+自己
 }

 void pushdown(int k)//要先pushdown爸爸才能pushdown儿子
 {
     int l=ch[k][],r=ch[k][];//左儿子和右儿子
     if(rev[k]){//翻转区间
         swap(ch[k][],ch[k][]);//翻转左右儿子
         rev[l]^=;rev[r]^=;//标记下传
         rev[k]=;//当前节点标记去掉
     }
 }

 void rotate(int x,int &k)//翻转操作
 {
     int y=pre[x],z=pre[y],l,r;
     if(ch[y][]==x) l=;
     else l=;
     r=l^;
     if(y==k) k=x;
     else{if(ch[z][]==y) ch[z][]=x;else ch[z][]=x;}
     pre[x]=z;pre[y]=x;pre[ch[x][r]]=y;
     ch[y][l]=ch[x][r];ch[x][r]=y;
     pushup(y);pushup(x);
 }

 void splay(int x,int &k)//splay到目标状态
 {
     while(x!=k){
         int y=pre[x],z=pre[y];
         if(y!=k){
             if(ch[y][]==x^ch[z][]==y)rotate(x,k);
             else rotate(y,k);
         }
         rotate(x,k);
     }
 }

 int find(int k,int rank)
 {
     pushdown(k);//有标记就pushdown
     int l=ch[k][],r=ch[k][];
     if(size[l]+==rank) return k;
     else if(size[l]>=rank) return find(l,rank);
     else return find(r,rank-size[l]-);
 }

 void change(int l,int r)
 {
     int x=find(rt,l),y=find(rt,r+);
     splay(x,rt);splay(y,ch[x][]);
     int z=ch[y][];
     rev[z]^=;
 }

 void build(int l,int r,int f)
 {
     if(l>r) return;
     int now=data[l],last=data[f];
     if(l==r){
         pre[now]=last;
         size[now]=;
         if(l<f) ch[last][]=now;
         else ch[last][]=now;
         return;
     }

     int mid=(l+r)>>;
     now=data[mid];
     build(l,mid-,mid);
     build(mid+,r,mid);
     pre[now]=last;
     pushup(mid);
     if(mid<f) ch[last][]=now;
     else ch[last][]=now;
 }

 int main()
 {
     scanf("%d%d",&n,&m);
     for(int i=;i<=n+;i++)
         data[i]=++sz;
     build(,n+,);//建树，建两个哨兵节点为1，n+2。
     rt=(n+)>>;//中点为rt
     for(int i=;i<=m;i++){
         scanf("%d%d",&l,&r);
         change(l,r);
     }
     for(int i=;i<=n+;i++)
         printf("%d ",find(rt,i)-);//去掉哨兵节点
     return ;
 }

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