[BZOJ3223]文艺平衡树无旋Treap

2023-08-16 09:20:34

3223: Tyvj 1729 文艺平衡树

Time Limit: 10 Sec Memory Limit: 128 MB

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

题解：

我为什么先做了维修数列再来做这道题……

本题是我之前一篇博文[您有新的未分配科技点] 无旋treap：从单点到区间（例题 BZOJ1500&NOI2005 维护数列）的例题的其中一个操作内容（翻转），

如果想看讲解的话，上面的链接有详细讲解，这里不再赘述，仅附上代码：

 #include <cstdio>

 #include <cstring>

 #include <ctime>

 #include <cstdlib>

 #include <iostream>

 using namespace std;

 const int N=;

 int n;

 struct Treap

 {

     Treap *ch[];

     int val,key,flip,size;

     Treap(){size=flip=val=;key=rand();ch[]=ch[]=NULL;}

     inline void update()

         {size=ch[]->size++ch[]->size;}

 }*null=new Treap(),*root=null,*stack[N],*x,*last;

 typedef pair<Treap*,Treap*> D;

 inline Treap* newTreap(int val)

 {

     Treap *o=new Treap();

     o->size=;o->val=val;

     o->ch[]=o->ch[]=null;

     return o;

 }

 inline void pushdown_flip(Treap *o)

 {

     if(o==null)return;

     if(o->flip)

     {

         o->flip^=;

         if(o->ch[]!=null)o->ch[]->flip^=;

         if(o->ch[]!=null)o->ch[]->flip^=;

         swap(o->ch[],o->ch[]);

     }

 }

 Treap* merge(Treap *a,Treap *b)

 {

     if(a==null)return b;

     if(b==null)return a;

     pushdown_flip(a);pushdown_flip(b);

     if(a->key < b->key)

         {a->ch[]=merge(a->ch[],b);a->update();return a;}

     else

         {b->ch[]=merge(a,b->ch[]);b->update();return b;}

 }

 D split(Treap *o,int k)

 {

     if(o==null)return D(null,null);

     pushdown_flip(o);D y;

     if(o->ch[]->size>=k)

         {y=split(o->ch[],k);o->ch[]=y.second;o->update();y.second=o;}

     else

         {y=split(o->ch[],k-o->ch[]->size-);o->ch[]=y.first;o->update();y.first=o;}

     return y;

 }

 inline Treap* build()

 {

     int p=;

     for(int i=;i<=n;i++)

     {

         x=newTreap(i);last=null;

         while(p&&stack[p]->key > x->key)

             {stack[p]->update();last=stack[p];stack[p--]=null;}

         if(p)stack[p]->ch[]=x;

         x->ch[]=last;stack[++p]=x;

     }

     while(p)stack[p--]->update();

     return stack[];

 }

 inline void dfs(Treap *o)

 {

     if(o==null)return;

     pushdown_flip(o);

     if(o->ch[]!=null)dfs(o->ch[]);

     printf("%d ",o->val);

     if(o->ch[]!=null)dfs(o->ch[]);

 }

 inline void reserve()

 {

     int l,r;scanf("%d%d",&l,&r);

     D x=split(root,r);

     D y=split(x.first,l-);

     if(y.second!=null)y.second->flip^=;

     root=merge(merge(y.first,y.second),x.second);

 }

 int main()

 {

     int m;scanf("%d%d",&n,&m);

     root=build();

     while(m--)reserve();

     dfs(root);

 }

码农公寓