bzoj3223 文藝平衡樹 treap

題意:求多次區間反轉後的序列

一眼splay，我用了可持久treap實作的。

速度也不錯 2008ms

這麼想想splay好像沒什麼用了(大霧@lct

#include<iostream>
#include<cstdio>
#include<cstdlib>
#define N 
#define mp make_pair
#define pa pair<int,int>
using namespace std;
struct treap{int val,ls,rs,sz,key,flip;}t[N];
int n,m,root=,num=,cnt=;
int v[N]; 
void pushdown(int x){
    if(!t[x].flip) return;
    t[t[x].ls].flip^=t[x].flip;
    t[t[x].rs].flip^=t[x].flip;
    t[x].flip=;
    swap(t[x].ls,t[x].rs);
}
void pushup(int x) {t[x].sz=t[t[x].ls].sz+t[t[x].rs].sz+;}
pa split(int a,int k){
    pa tmp;
    if(k==) return mp(,a);
    pushdown(a);int ls=t[a].ls,rs=t[a].rs;
    if(k==t[ls].sz) {t[a].ls=;pushup(a);return mp(ls,a);}
    if(k==t[ls].sz+) {t[a].rs=;pushup(a);return mp(a,rs);}
    if(k<t[ls].sz) {tmp=split(ls,k);t[a].ls=tmp.second;pushup(a);return mp(tmp.first,a);}
    if(k>t[ls].sz+) {tmp=split(rs,k-t[ls].sz-);t[a].rs=tmp.first;pushup(a);return mp(a,tmp.second);}
}
int merge(int a,int b){
    if(a== || b==) return a+b;
    if(t[a].key<t[b].key) {pushdown(a);t[a].rs=merge(t[a].rs,b);pushup(a);return a;}
    else {pushdown(b);t[b].ls=merge(a,t[b].ls);pushup(b);return b;}
}
void ins(int &now,int x){
    t[++num].val=x;
    t[num].key=rand();
    t[num].sz=;
    pushdown(now);
    now=merge(now,num);
}
void dfs(int x){
    if(x==) return;
    if(t[x].flip) pushdown(x);
    dfs(t[x].ls);
    v[++cnt]=x;
    dfs(t[x].rs);
}
int main(){
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=;i<=n;i++) ins(root,i);
    for(int i=;i<=m;i++){
        int l,r;
        scanf("%d%d",&l,&r);
        pa tmp1=split(root,l-);
        pa tmp2=split(tmp1.second,r-l+);
        t[tmp2.first].flip^=;
        root=merge(tmp1.first,tmp2.first);
        root=merge(root,tmp2.second);
    }
    dfs(root);
    for(int i=;i<=cnt;i++) printf("%d ",v[i]);puts("");
    return ;
}