【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 ;
}