bzoj 3223: Tyvj 1729 文藝平衡樹

Description

您需要寫一種資料結構（可參考題目标題），來維護一個有序數列，其中需要提供以下操作：翻轉一個區間，例如原有序序列是5 4 3 2 1，翻轉區間是[2,4]的話，結果是5 2 3 4 1

解題報告:

史前巨坑，splay還是打的不熟..

對于這個題以編号為關鍵字排序建平衡樹區間反轉即對應交換左右子節點,打上lazy标記即可

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define RG register
#define il inline
#define iter iterator
#define Max(a,b) ((a)>(b)?(a):(b))
#define Min(a,b) ((a)<(b)?(a):(b))
using namespace std;
const int N=100005;
int n,m,fa[N],ch[N][2],root=0,sz[N];
bool rev[N];
void upd(int rt){if(rt)sz[rt]=sz[ch[rt][0]]+sz[ch[rt][1]]+1;}
void pushdown(int rt){
    if(!rev[rt] || !rt)return ;
    int ls=ch[rt][0],rs=ch[rt][1];
    rev[ls]^=1;rev[rs]^=1;
    swap(ch[ls][0],ch[ls][1]);swap(ch[rs][0],ch[rs][1]);
    rev[rt]=0;
}
void rotate(int x,bool t){
    int y=fa[x];
    ch[y][!t]=ch[x][t];fa[ch[x][t]]=y;
    ch[fa[y]][ch[fa[y]][1]==y]=x;
    ch[x][t]=y;fa[x]=fa[y];fa[y]=x;
    upd(y);upd(x);
}
void Splay(int x,int g){
    while(fa[x]!=g){
        pushdown(fa[x]);pushdown(x);
        if(fa[fa[x]]==g)rotate(x,ch[fa[x]][0]==x);
        else{
            int par=fa[x];bool t=(ch[fa[par]][0]==par);
            if((ch[fa[x]][0]==x)==t)rotate(par,t);
            else rotate(x,!t);
            rotate(x,t);
        }
    }
    if(!g)root=x;
}
int getrank(int x,int rk){
    pushdown(x);
    if(sz[ch[x][0]]+1==rk)return x;
    if(sz[ch[x][0]]>=rk)return getrank(ch[x][0],rk);
    return getrank(ch[x][1],rk-sz[ch[x][0]]-1);
}
void reser(int l,int r){
    int x=getrank(root,l),y=getrank(root,r+1);
    Splay(x,0);Splay(y,x);
    int p=ch[y][0];
    swap(ch[p][0],ch[p][1]);
    rev[p]^=1;
}
void build(int &rt,int l,int r){
    int mid=(l+r)>>1;
    rt=mid;sz[rt]=1;
    if(l==r)return ;
    if(l<mid)build(ch[rt][0],l,mid-1),fa[ch[rt][0]]=rt;
    if(mid<r)build(ch[rt][1],mid+1,r),fa[ch[rt][1]]=rt;
    upd(rt);
}
void work()
{
    scanf("%d%d",&n,&m);
    build(root,1,n+2);
    int l,r;
    for(int i=1;i<=m;i++)
        scanf("%d%d",&l,&r),reser(l,r+1);
    for(int i=1;i<=n;i++)
        printf("%d ",getrank(root,i+1)-1);
}

int main()
{
    work();
    return 0;
}
                

轉載于:https://www.cnblogs.com/Yuzao/p/7544875.html