【BZOJ 3223】文藝平衡樹

Description

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

N,M<=100000

Analysis

splay拿來練翻轉

這題就隻用支援翻轉，很裸

翻轉區間[x,y]的操作：

提取該區間，打一個bool類型的lazy tag，值為1表示該區間要翻轉。

翻轉兩次一個區間相當于不翻轉，是以打标記的代碼是bz[x]=bz[x] xor 1

當以後做的時候走到這個點，就要先down一下标記，具體過程是交換其兩個子樹，标記下傳，該點标記清空。

也就是線段樹lazy tag的思想。當然提取區間需要維護size，需要查找區間第k個元素

注意，因為有區間翻轉操作，是以kth的時候要下傳标記，要不然會找錯。

Code

#include<cstdio>
#include<algorithm>
#define fo(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
const int N=;
int n,m,top,root,t[N][],f[N],size[N];
bool bz[N];
bool pd(int x)
{
    return x==t[f[x]][];
}
void update(int x)
{
    size[x]=size[t[x][]]+size[t[x][]]+;
}
void down(int x)
{
    if(!bz[x]) return;
    swap(t[x][],t[x][]);
    bz[t[x][]]^=,bz[t[x][]]^=;
    bz[x]=;
}
void rotate(int x)
{
    int y=f[x],z=pd(x);
    t[y][z]=t[x][-z];
    if(t[y][z]) f[t[y][z]]=y;
    f[x]=f[y];
    if(f[x]) t[f[x]][pd(y)]=x;
    f[y]=x,t[x][-z]=y;
    update(y);
}
void splay(int x,int y)
{
    while(f[x]!=y)
    {
        if(f[f[x]]!=y)
            if(pd(x)==pd(f[x])) rotate(f[x]);
            else rotate(x);
        rotate(x);
    }
    update(x);
    if(!y) root=x;
}
int kth(int x,int k)
{
    down(x);
    if(size[t[x][]]+==k) return x;
    if(k>size[t[x][]]) return kth(t[x][],k-size[t[x][]]-);
    else return kth(t[x][],k);
}
void turn(int l,int r)
{
    int x=kth(root,l-),
    y=kth(root,r+);
    splay(x,),splay(y,x);
    bz[t[y][]]^=;
}
int main()
{
    int x,y,l,r;
    scanf("%d %d",&n,&m);
    fo(i,,n) f[i]=i+,t[i+][]=i;
    f[n+]=n+,t[n+][]=n+;
    fo(i,,n+) size[i]=i;
    root=n+;
    fo(i,,m)
    {
        scanf("%d %d",&x,&y),x++,y++;
        turn(x,y);
    }
    fo(i,,n+) printf("%d ",kth(root,i)-);
    return ;
}