Tyvj P1729 文艺平衡树 Splay

题目: http://tyvj.cn/p/1729

P1729 文艺平衡树

时间: 1000ms / 空间: 131072KiB / Java类名: Main

背景

此为平衡树系列第二道：文艺平衡树

描述

您需要写一种数据结构（可参考题目标题），来维护一个有序数列，其中需要提供以下操作：
翻转一个区间，例如原有序序列是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次变换后的结果

测试样例1

输入

5 3
1 3
1 3
1 4

输出

4 3 2 1 5

备注

n,m<=100000

题解：

Splay

复习一下Splay。

  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 #define MAXN 100010
  4 struct node
  5 {
  6     int left,right,size,val;
  7 }tree[MAXN];
  8 int rev[MAXN],father[MAXN],a[MAXN];
  9 int read()
 10 {
 11     int s=0,fh=1;char ch=getchar();
 12     while(ch<'0'||ch>'9'){if(ch=='-')fh=-1;ch=getchar();}
 13     while(ch>='0'&&ch<='9'){s=s*10+(ch-'0');ch=getchar();}
 14     return s*fh;
 15 }
 16 void Pushup(int k)
 17 {
 18     tree[k].size=tree[tree[k].left].size+tree[tree[k].right].size+1;
 19 }
 20 void Pushdown(int k)
 21 {
 22     int l=tree[k].left,r=tree[k].right;
 23     if(rev[k]!=0)
 24     {
 25         rev[k]^=1;rev[l]^=1;rev[r]^=1;
 26         swap(tree[k].left,tree[k].right);
 27     }
 28 }
 29 void Build(int l,int r,int f)
 30 {
 31     if(l>r)return;
 32     int now=l,last=f;
 33     if(l==r)
 34     {
 35         father[now]=last;tree[now].size=1;tree[now].val=a[l];
 36         if(l<f)tree[last].left=now;
 37         else tree[last].right=now;
 38         return;
 39     }
 40     int mid=(l+r)/2;
 41     now=mid;
 42     Build(l,mid-1,mid);Build(mid+1,r,mid);
 43     tree[now].val=a[mid];
 44     father[now]=last;Pushup(now);
 45     if(mid<f)tree[last].left=now;
 46     else tree[last].right=now;
 47 }
 48 void Rotate(int x,int &root)
 49 {
 50     int y=father[x],z=father[y];
 51     if(y==root)root=x;
 52     else
 53     {
 54         if(tree[z].left==y)tree[z].left=x;
 55         else tree[z].right=x;
 56     }
 57     if(tree[y].left==x)
 58     {
 59         father[x]=z;father[y]=x;tree[y].left=tree[x].right;tree[x].right=y;father[tree[y].left]=y;
 60     }
 61     else
 62     {
 63         father[x]=z;father[y]=x;tree[y].right=tree[x].left;tree[x].left=y;father[tree[y].right]=y;
 64     }
 65     Pushup(y);Pushup(x);
 66 }
 67 void Splay(int x,int &root)
 68 {
 69     int y,z;
 70     while(x!=root)
 71     {
 72         y=father[x];z=father[y];
 73         if(y!=root)
 74         {
 75             if((tree[y].left==x)^(tree[z].left==y))Rotate(x,root);
 76             else Rotate(y,root);
 77         }
 78         Rotate(x,root);
 79     }
 80 }
 81 int Find(int k,int rank)
 82 {
 83     Pushdown(k);
 84     int l=tree[k].left,r=tree[k].right;
 85     if(rank==tree[l].size+1)return k;
 86     if(rank<=tree[l].size)return Find(l,rank);
 87     else return Find(r,rank-tree[l].size-1);
 88 }
 89 int main()
 90 {
 91     int n,m,i,nn,s1,s2,x,y,z,rt;
 92     n=read();m=read();nn=n;
 93     for(i=2;i<=n+1;i++)a[i]=i-1;
 94     rt=(1+n+2)/2;Build(1,n+2,0);
 95     for(i=1;i<=m;i++)
 96     {
 97         s1=read();s2=read();
 98         x=Find(rt,s1);y=Find(rt,s2+2);
 99         Splay(x,rt);Splay(y,tree[x].right);
100         z=tree[y].left;rev[z]^=1;
101     }
102     for(i=1;i<=n;i++)
103     {
104         //printf("%d ",Find(rt,i)-1);
105         x=Find(rt,i);y=Find(rt,i+2);
106         Splay(x,rt);Splay(y,tree[x].right);
107         z=tree[y].left;
108         printf("%d ",tree[z].val);
109     }
110     fclose(stdin);
111     fclose(stdout);
112     return 0;
113 }