BZOJ3223: Tyvj 1729 文艺平衡树（洛谷P3391）

Splay

BZOJ题目传送门

洛谷题目传送门

平衡树维护序列，翻转区间即相当于交换左右子树，打个Lazy-Tag就行，感觉比书架简单。。。

代码：

#include<cctype>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 100000
using namespace std;
struct node{
    int to[],fa,size;
}t[N+];
int n,m,nd,rt,id[N+];
bool lazy[N+];
inline char readc(){//读优
    static char buf[],*l=buf,*r=buf;
    if (l==r) r=(l=buf)+fread(buf,,,stdin);
    if (l==r) return EOF; return *l++;
}
inline int _read(){
    int num=; char ch=readc();
    while (!isdigit(ch)) ch=readc();
    while (isdigit(ch)) num=num*+ch-,ch=readc();
    return num;
}
void pushup(int x){ t[x].size=t[t[x].to[]].size+t[t[x].to[]].size+; }
void pushdown(int x){//下传标记
    if (!lazy[x]) return;
    int l=t[x].to[],r=t[x].to[];
    swap(t[x].to[],t[x].to[]);//翻转左右子树
    lazy[l]^=,lazy[r]^=,lazy[x]=;
}
void rtt(int x,int &w){
    int y=t[x].fa,z=t[y].fa,p=(t[y].to[]!=x);
    if (y==w) w=x;
    else t[z].to[t[z].to[]!=y]=x;
    t[x].fa=z,t[y].fa=x,t[t[x].to[p^]].fa=y;
    t[y].to[p]=t[x].to[p^],t[x].to[p^]=y;
    pushup(y),pushup(x);
}
void splay(int x,int &w){
    while (x!=w){
        int y=t[x].fa,z=t[y].fa;
        if (y!=w)
            if (t[y].to[]==x^t[z].to[]==y) rtt(x,w);
            else rtt(y,w);
        rtt(x,w);
    }
}
void build(int l,int r,int fa){//建树
    if (l>r) return;
    if (l==r){
        t[id[l]].size=,t[id[l]].fa=fa;
        t[fa].to[l>fa]=id[l]; return;
    }
    int mid=(l+r)>>;
    build(l,mid-,mid),build(mid+,r,mid);
    t[id[mid]].fa=fa,pushup(mid);
    t[fa].to[mid>fa]=id[mid];
}
int srch(int x,int w){//查找第w大的数
    pushdown(x); int p=t[x].to[];
    if (t[p].size+==w) return x;
    if (t[p].size>=w) return srch(p,w);
    return srch(t[x].to[],w-t[p].size-);
}
void nsrt(int l,int r){//翻转
    int x=srch(rt,l),y=srch(rt,r+);
    splay(x,rt),splay(y,t[x].to[]);//分别把l-1,r+1伸展到根和右子树
    lazy[t[y].to[]]^=;//l~r这段区间对应的就是y的左子树
}
int main(){
    n=_read(),m=_read();
    for (int i=;i<=n+;i++) id[i]=++nd;//这道题的初始序列就是1~n。
    build(,n+,),rt=(n+)>>;//这里要加两个虚拟节点拿来伸展
    while (m--){
        int l=_read(),r=_read();
        nsrt(l,r);
    }
    for (int i=;i<=n+;i++)
        printf("%d ",srch(rt,i)-);//记得减1
    return printf("\n"),;
}