【BZOJ3233】【tyvj1729】文艺平衡树

原题传送门

解题思路:裸平衡树操作,支持区间翻转即可,这里写了无旋treap。

其实平衡树的区间操作就和线段树差不多,你用个标记搞一下就好了,,,,,

#include <stdio.h>
#define r register
#define getchar() (S==TT&&(TT=(S=BB)+fread(BB,1,1<<15,stdin),S==TT)?EOF:*S++)
char BB[<<],*TT=BB,*S=BB;
inline int read(){
int x=,f=;char ch=getchar();
while (ch<''||ch>'') f=ch=='-'?-:,ch=getchar();
while (ch>=''&&ch<='') x=(x<<)+(x<<)+ch-'',ch=getchar();
return x*f;
}
namespace Treap{
inline int Rand(){
static int x=;
return x^=x<<,x^=x>>,x^=x<<;
}
struct node{
node *ls,*rs;
int val,sz,pri;
bool rev;
node(int x):val(x),rev(),sz(),pri(Rand()){ls=rs=NULL;}
void combine(){sz=(ls?ls->sz:)+(rs?rs->sz:)+;}
}*root;
struct Droot{node *a,*b;};
inline int Size(node *x){return x?x->sz:;}
inline void swap(node *&x,node *&y){r node *t=x;x=y;y=t;}
inline node *reverse(node *x){if (!x) return NULL;swap(x->ls,x->rs);x->rev^=;return x;}
inline void pushdown(node *x){if (x->rev) reverse(x->ls),reverse(x->rs),x->rev=;}
node *merge(node*a,node*b){
if (!a) return b;if (!b) return a;
if (a->pri<b->pri){
pushdown(a);a->rs=merge(a->rs,b);
a->combine();return a;
}else{
pushdown(b);b->ls=merge(a,b->ls);
b->combine();return b;
}
}
Droot split(node *x,int k){
if (x==NULL) return (Droot){NULL,NULL};
r Droot y;pushdown(x);
if (k<=Size(x->ls)){
y=split(x->ls,k);x->ls=y.b;
x->combine();y.b=x;
}else{
y=split(x->rs,k-Size(x->ls)-);
x->rs=y.a;x->combine();y.a=x;
}return y;
}
inline void Reverse(int L,int R){
r Droot x=split(root,L-);
r Droot y=split(x.b,R-L+);
root=merge(merge(x.a,reverse(y.a)),y.b);
}
}using namespace Treap;
int n,q;
void init(){
n=read(),q=read();
for (int i=; i<=n; ++i) root=merge(root,new node(i));
}
void solve(){
while(q--){
r int L=read(),R=read();
Reverse(L,R);
}for (r int i=; i<=n; ++i) {
r Droot y=split(root,);
printf("%d ",y.a->val);
root=y.b;
}
}
int main(){init(); solve(); return ;}
上一篇:asp.net 2.0 Session丢失问题


下一篇:NGINX宏观手记(变量|配置)