【bzoj3223】Tyvj 1729 文艺平衡树

2015.06.11 12:51 Thu | 46次阅读 | 旧日oi | 固定链接 | 源码

Description

 您需要写一种数据结构(可参考题目标题),来维护一个有序数列,其中需要提供以下操作:翻转一个区间,例如原有序序列是5 4 3 2 1,翻转区间是[2,4]的话,结果是5 2 3 4 1

题解

看到wzh把这题A了,顺手写一发……写完之后才发现我以前写过……最后不能加换行……

我的程序

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define N 100005
#define is(x) (son[fa[x]][1]==x)
#define key son[son[root][1]][0]
int n,m,cnt,root,num;
int fa[N],val[N],siz[N],rev[N],son[N][2];
int ans[N];
void newnode(int &x,int v,int f)
{   
    x=++cnt;
    fa[x]=f;val[x]=v;
    siz[x]=1;
}
void pushup(int x)
{
    siz[x]=siz[son[x][0]]+siz[son[x][1]]+1;
}
void build(int &x,int l,int r,int f)
{
    if(l>r) return;
    int mid=(l+r)>>1;
    newnode(x,mid,f);
    build(son[x][0],l,mid-1,x);
    build(son[x][1],mid+1,r,x);
    pushup(x);
}
void link(int x,int y,int d)
{
    fa[x]=y;son[y][d]=x;
}
void rotate(int x)
{
    int y=fa[x],z=fa[y],id=is(x),t=son[x][!id];
    link(x,z,is(y));link(y,x,!id);link(t,y,id);
    son[0][0]=son[0][1]=fa[0]=0;
    pushup(y);pushup(x);
}
void reverse(int x)
{
    if(!x) return ;
    swap(son[x][0],son[x][1]);
    rev[x]^=1;
}
void pushdown(int x)
{
    if(rev[x])
    {
        reverse(son[x][0]);
        reverse(son[x][1]);
        rev[x]=0;
    }
}
void splay(int x,int g)
{
    while(fa[x]!=g)
    {
        int y=fa[x],z=fa[y];
        if(z==g)
        {
            pushdown(y);pushdown(x);
            rotate(x);
            break;
        }
        pushdown(z);pushdown(y);pushdown(x);
        rotate(is(y)==is(x)?y:x);rotate(x);
    }
    if(!g) root=x;
}
void Init()
{
    newnode(root,0,0);
    newnode(son[root][1],0,root);
    build(key,1,n,son[root][1]);
    pushup(son[root][1]);pushup(root);
}
int find(int v)
{
    int x=root;
    while(x)
    {
        pushdown(x);
        if(siz[son[x][0]]+1==v) return x;
        if(siz[son[x][0]]>=v) x=son[x][0];
        else v-=siz[son[x][0]]+1,x=son[x][1];
    }
}
void dfs(int x)
{
    pushdown(x);
    if(son[x][0]) dfs(son[x][0]);
    ans[++num]=val[x];
    if(son[x][1]) dfs(son[x][1]);
}
int main()
{
    cin>>n>>m;
    Init();
    for(int l,r,i=1;i<=m;i++)
    {
        scanf("%d%d",&l,&r);
        splay(find(l),0);
        splay(find(r+2),root);
        reverse(key);
    }
    splay(find(1),0);
    splay(find(n+2),root);
    dfs(key);
    for(int i=1;i<num;i++) printf("%d ",ans[i]);
    printf("%d",ans[num]);
}```