首页 > 代码库 > TYVJ1729文艺平衡树

TYVJ1729文艺平衡树

2024-07-13 05:53:57   221人阅读

传送门：http://tyvj.cn/Problem_Show.aspx?id=1729

 

文艺平衡树
From admin
 
 
背景 Background
此为平衡树系列第二道：文艺平衡树
 
 
描述 Description
您需要写一种数据结构（可参考题目标题），来维护一个有序数列，其中需要提供以下操作：
翻转一个区间，例如原有序序列是5 4 3 2 1，翻转区间是[2,4]的话，结果是5 2 3 4 1
 
 
输入格式 InputFormat
第一行为n,m n表示初始序列有n个数，这个序列依次是(1,2……n-1,n)  m表示翻转操作次数
接下来m行每行两个数[l,r] 数据保证 1<=l<=r<=n
 
 
输出格式 OutputFormat
输出一行n个数字，表示原始序列经过m次变换后的结果
 
 
样例输入 SampleInput [复制数据]
 
 
样例输出 SampleOutput [复制数据]
 
 
数据范围和注释 Hint

n,m<=100000

 

 

做法：Splay对区间的操作、lazy标记。 我一直没懂这个splay的操作，对区间[a,b]的操作，首先把a-1splay到树根，然后再把b+1旋转到树根的右子树。这个很好理解，但是我一开始写的是直接T[i].s[v>T[i].v]访问，一直不对，一直很纳闷，后来模拟了一下，才发现真正有效的是splay的排名，lazy标记下传后，左右子树被交换，但默认的排名未变。即第i号元素不一定就是i。

 

Codes:(再次orz squarefk)

 1 #include <set> 2 #include <cmath> 3 #include <queue> 4 #include <cstdio> 5 #include <cstdlib> 6 #include <cstring> 7 #include <iostream> 8 #include <algorithm> 9 using namespace std;10 const int N = 100010;11 #define fa(i) (T[i].p)12 #define Ch1 (T[i].s[0])13 #define Ch2 (T[i].s[1])14 #define Loc(i) (T[fa(i)].s[1]==i)15 #define Sets(a,b,c) {T[a].s[c] = b;fa(b) = a;}16 #define For(i,n) for(int i=1;i<=n;i++)17 #define Rep(i,l,r) for(int i=l;i<=r;i++)18 19 struct tnode{20     int s[2],size,p,V,flag;21 }T[N];22 23 int ttot,l,r,n,m,root;24 25 void Pushdown(int i){26     if(T[i].flag){27         if(Ch1) T[Ch1].flag ^= 1;28         if(Ch2) T[Ch2].flag ^= 1;29         swap(Ch1,Ch2);30         T[i].flag = 0;31     }32 }33 34 void Build(int l,int r,int p,int &i){35     if(l>r) return;36     int m = ( l + r ) >> 1;37     T[i=++ttot].V = m;38     T[i].p = p; T[i].size = 1;39     Build(l,m-1,i,Ch1);40     Build(m+1,r,i,Ch2);41     T[i].size = T[Ch1].size + T[Ch2].size + 1;42 }43 44 void Rot(int x){45     int y = fa(x) , z = fa(y);46     Pushdown(y);Pushdown(x);47     int lx = Loc(x) , ly = Loc(y);48     Sets(y,T[x].s[!lx],lx);49     Sets(z,x,ly);50     Sets(x,y,!lx);51     T[y].size = T[T[y].s[0]].size + T[T[y].s[1]].size + 1;52 }53 54 void Splay(int i,int goal){55     while(fa(i)!=goal){56         if(fa(fa(i))!=goal) Rot(fa(i));57         Rot(i);58     }59     T[i].size = T[Ch1].size + T[Ch2].size + 1;60     if(!goal) root = i;61 }62 63 int Find(int i,int rank){64     Pushdown(i);65     if(T[Ch1].size + 1 == rank) return i;66     else if(T[Ch1].size>= rank) return Find(Ch1,rank);67     else                        return Find(Ch2,rank-T[Ch1].size-1);68 }69 70 void OUT(int i,int rank){71     if(!i) return;72     Pushdown(i);73     OUT(Ch1,rank);74     rank+=T[Ch1].size+1;75     if((rank!=1)&&(rank!=n+2)){76         if(rank==n+1) printf("%d\n",T[i].V);77         else          printf("%d ",T[i].V);78     }79     OUT(Ch2,rank);80 }81 82 83 int main(){84     scanf("%d%d",&n,&m);85     Build(0,n+1,0,root);86     For(i,m){87         scanf("%d%d",&l,&r);88         Splay(Find(root,l),0);89         Splay(Find(root,r+2),root);90         T[T[T[root].s[1]].s[0]].flag ^= 1;91     }92     OUT(root,0);93     return 0;94 }


联系
我们