首页 > 代码库 > [bzoj3223]文艺平衡树

[bzoj3223]文艺平衡树

2024-08-15 02:53:07   219人阅读

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

 

这种动态维护数列的题目一般都可以用splay做；

具体方法是加一个lazy标记，然后往下find的时候的时候交换一下左右子树；

代码：

技术分享
 1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<string> 5 #include<algorithm> 6 #include<cstdlib> 7 using namespace std; 8 #define mid ((left+right)>>1) 9 const int maxn=101000;10 int cnt=0,root=0;11 int n,m;12 struct node{13     int ch[2],key,flag,fa,siz;14 }e[maxn];15 void updata(int x){e[x].siz=e[e[x].ch[0]].siz+e[e[x].ch[1]].siz+1;}16 void downdata(int x){swap(e[x].ch[0],e[x].ch[1]);e[e[x].ch[0]].flag^=1;e[e[x].ch[1]].flag^=1;e[x].flag^=1;}17 void rotate(int x,int d){18     int y=e[x].fa;19     e[x].fa=e[y].fa;e[y].fa=x;e[e[x].ch[d^1]].fa=y;20     e[y].ch[d]=e[x].ch[d^1];e[x].ch[d^1]=y;21     if(e[x].fa)e[e[x].fa].ch[e[e[x].fa].ch[1]==y]=x;22     updata(y);updata(x);23 }24 void splay(int x,int S){25     while(e[x].fa!=S){26         if(e[e[x].fa].fa==S)rotate(x,e[e[x].fa].ch[1]==x);27         else {28             int y=e[x].fa;29             int z=e[y].fa;30             int d=(e[z].ch[1]==y);31             if((e[y].ch[d]==x)){rotate(y,d);32             rotate(x,d);}33             else {rotate(x,d^1);rotate(x,d);}34         }35     }36     if(!S)root=x;37 }38 int build(int left,int right,int fa){39     if(left>right)return 0;40     int x=++cnt;e[x].fa=fa;e[x].key=mid;e[x].siz=1;41     e[x].ch[0]=build(left,mid-1,x);42     e[x].ch[1]=build(mid+1,right,x);43     updata(x);44     return x;45 }46 int find(int k){47     int x=root;48     while(x){49         if(e[x].flag)downdata(x);50         if(e[e[x].ch[0]].siz+1==k)return x;51         if(e[e[x].ch[0]].siz+1>k)x=e[x].ch[0];52         else k-=(e[e[x].ch[0]].siz+1),x=e[x].ch[1];53     }54     splay(x,0);55     return x;56 }57 void print(int x){58     if(!x)return;59     if(e[x].flag)downdata(x);60     print(e[x].ch[0]);61     if(e[x].key!=0&&e[x].key!=n+1)printf("%d ",e[x].key);62     print(e[x].ch[1]);63 }64 int main(){65     freopen("1.in","r",stdin);66     freopen("1.out","w",stdout);67     scanf("%d%d",&n,&m);68     root=build(0,n+1,0);69     int x,y;70     while(m--){71         scanf("%d%d",&x,&y);72         x=find(x);y=find(y+2);73         splay(x,0);splay(y,x);74         e[e[y].ch[0]].flag^=1;75     }76     print(root);77     return 0;78 }
View Code

 

[bzoj3223]文艺平衡树


联系
我们