BZOJ 3223 Tyvj 1729 문예 평형 수

설명 은 데이터 구조 (제목 참조) 를 써 서 질서 있 는 수열 을 유지 해 야 합 니 다. 그 중에서 다음 과 같은 조작 을 제공 해 야 합 니 다. 예 를 들 어 기 존의 순서 서열 은 5, 4, 3, 2 1 이 고 뒤 집기 구간 은 [2, 4] 이 라면 결 과 는 5, 2, 3, 4 1 입 니 다.
[제목 분석] 다른 제목: 필요 해...이 문제: 필요 합 니 다...BZOJ 가 문 제 를 아주 패기 있 게 베 꼈 다.Splay + 구간 뒤 집기 표시 (Splay 는 Treap 보다 시 리 즈 를 잘 쓴다) 를 잊 어 버 리 면 됩 니 다. 이 문제 도 옆집 SilverNebula 에서 찾 은 것 입 니 다.%.
【 코드 】

#include 
#include 
#include 
#include 

#include 
#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;

#define maxn 1000005
#define inf (0x3f3f3f3f)

int read()
{
    int x=0,f=1; char ch=getchar();
    while (ch<'0'||ch>'9') {if (ch=='-') f=-1; ch=getchar();}
    while (ch>='0'&&ch<='9') {x=x*10+ch-'0'; ch=getchar();}
    return x*f;
}

int n,m,l,r;
int fa[maxn],ch[maxn][2],num[maxn],siz[maxn],rev[maxn],rt,tot,a[maxn];

void update(int k)
{
    siz[k]=siz[ch[k][0]]+siz[ch[k][1]]+1;
}

int build(int l,int r,int lst)
{
    if (l>r) return 0;
    int k=++tot;
//  printf("%d %d - %d
",k,l,r);
    fa[k]=lst;
    if (l==r)
    {
        ch[k][0]=ch[k][1]=0;
        siz[k]=1;
        rev[k]=0;
        num[k]=a[l];
        return k;
    }
    int mid=(l+r)/2;
    rev[k]=0;
    num[k]=a[mid];
    ch[k][0]=build(l,mid-1,k);
    ch[k][1]=build(mid+1,r,k);
    update(k);
    return k;
}

void rot(int x,int &k)
{
//  printf("rot");
    int y=fa[x],z=fa[y],l,r;
    if (ch[y][0]==x) l=0; else l=1;
    r=l^1;
    if (y==k) k=x;
    else
    {
        if (ch[z][0]==y) ch[z][0]=x;
        else ch[z][1]=x;
    }
    fa[x]=z; fa[y]=x; fa[ch[x][r]]=y;
    ch[y][l]=ch[x][r]; ch[x][r]=y;
    update(y); update(x);
}

void pushdown(int k)
{
    if (rev[k])
    {
        rev[k]^=1;
        rev[ch[k][0]]^=1;
        rev[ch[k][1]]^=1;
        swap(ch[k][0],ch[k][1]);
    }
}

void splay(int x,int &k)
{
//  printf("sp
");
    while (x!=k)
    {
        int y=fa[x],z=fa[y];
        if (y!=k)
        {
            if (ch[y][0]==x^ch[z][0]==y) rot(y,k);
            else rot(x,k);
        }
        rot(x,k);
    }
}

int find(int k,int x)
{
    pushdown(k);
    if (siz[ch[k][0]]+1==x) return k;
    else if (x<=siz[ch[k][0]]) return find(ch[k][0],x);
    else return find(ch[k][1],x-siz[ch[k][0]]-1);
}

void dfs(int k)
{
    pushdown(k);
    if (!k)return ;
    dfs(ch[k][0]);
    if (num[k]!=0)
    printf("%d ",num[k]);
    dfs(ch[k][1]);
}

int main()
{
    n=read();m=read();
    for (int i=1;i<=n;++i) a[i+1]=i;
    rt=build(1,n+2,0);
//  printf("rt is %d
",rt);
    while (m--)
    {
//      for (int i=1;i<=n+2;++i) printf("%d ",i); printf("
");
//      for (int i=1;i<=n+2;++i) printf("%d ",ch[i][0]); printf("
");
//      for (int i=1;i<=n+2;++i) printf("%d ",ch[i][1]); printf("
");
//      for (int i=1;i<=n+2;++i) printf("%d ",fa[i]); printf("
");
//      for (int i=1;i<=n+2;++i) printf("%d ",num[i]); printf("
");
//      for (int i=1;i<=n+2;++i) printf("%d ",rev[i]); printf("
");
//      dfs(rt);
        l=read();r=read();
        int x=find(rt,l),y=find(rt,r+2);
//      printf("%d %d
",x,y);
        splay(x,rt);splay(y,ch[x][1]);
        rev[ch[y][0]]^=1;
//      printf("over
");
    }
    dfs(rt);
}