BZOJ 3223 Tyvj 1729 文艺平衡树 | Splay 维护序列关系

题解:

每次reverse(l,r)

把l-1转到根,r+1变成他的右儿子,给r+1的左儿子打个标记就是一次反转操作了

每次find和dfs输出的时候下放标记,把左儿子和右儿子换一下

记得建树的时候建0到n+1

#include<cstdio>

#include<algorithm>

#include<cstring>

#define N 100010

#define which(x) (ls[fa[(x)]]==(x))

using namespace std;

int sz[N],ls[N],rs[N],fa[N],n,m,root,flag[N],id[N],idx;

void upt(int x) {sz[x]=+sz[ls[x]]+sz[rs[x]];}

int read()

{

    int ret=,neg=;

    char j=getchar();

    for (;j>'' || j<'';j=getchar())

    if (j=='-') neg=-;

    for (;j>='' && j<='';j=getchar())

    ret=ret*+j-'';

    return ret*neg;

}

void write(int x)

{

    if (x<) x=-x;

    if (x>=) write(x/);

    putchar(x%+'');

}

void swap_son(int u)

{

    if (!u) return;

    flag[u]^=;

    swap(ls[u],rs[u]);

    upt(u);

}

void pushdown(int u)

{

    if (!flag[u]) return ;

    swap_son(ls[u]),swap_son(rs[u]);

    flag[u]=;

}

int Build(int l, int r)

{

    int mid=l+r>>,u=++idx;

    id[u]=mid;

    if(mid>l) ls[u]=Build(l,mid-),fa[ls[u]]=u;

    if(mid<r) rs[u]=Build(mid+,r),fa[rs[u]]=u;

    upt(u);

    return u;

}

void Rotate(int u)

{

    int v=fa[u],w=fa[v],b=which(u)?rs[u]:ls[u];

    if(w) which(v)?ls[w]=u:rs[w]=u;

    which(u)?(ls[v]=b,rs[u]=v):(rs[v]=b,ls[u]=v);

    fa[u]=w,fa[v]=u;

    if(b) fa[b]=v;

    upt(v),upt(u);

}

void Splay(int u, int tar)

{

    while(fa[u] != tar)

    {

    if(fa[fa[u]] != tar)

    {

        if(which(u) == which(fa[u])) Rotate(fa[u]);

        else Rotate(u);

    }

    Rotate(u);

    }

    if(!tar) root = u;

}

int find(int k)

{

    int u=root;

    pushdown(u);

    while (sz[ls[u]]+!=k && u)

    {

    if (sz[ls[u]]>=k) u=ls[u];

    else k-=sz[ls[u]]+,u=rs[u];

    pushdown(u);

    }

    return u;

}

void rev(int l,int r)

{

    int u=find(l-),v=find(r+);

    Splay(u,);

    Splay(v,u);

    swap_son(ls[rs[root]]);

}

void dfs(int u)

{

    pushdown(u);

    if (ls[u]) dfs(ls[u]);

    if (id[u]> && id[u]<n+) write(id[u]-),putchar(' ');

    if (rs[u]) dfs(rs[u]);

}

int main()

{

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

    root=Build(,n+);

    for (int i=,l,r;i<=m;i++)

    l=read(),r=read(),rev(l+,r+);

    dfs(root);

    return ;

}