[BZOJ3223]文艺平衡树 无旋Treap

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);
}
上一篇:Luogu 3369 / BZOJ 3224 - 普通平衡树 - [无旋Treap]


下一篇:无旋treap的简单思想以及模板