文艺平衡树

您需要写一种数据结构（可参考题目标题），来维护一个有序数列。

其中需要提供以下操作：翻转一个区间，例如原有序序列是 \(5\ 4\ 3\ 2\ 1\)，翻转区间是 \([2,4]\) 的话，结果是 \(5\ 2\ 3\ 4\ 1\)。

我们以FHQ举例。

因为是区间的旋转，类似线段树，我们也需要一个懒标记

struct node{
    int l,r,val,key,size,tag;
}tr[N];

我们还需要一个下传标记的东西。

我们需要在分裂、合并、输出时下传标记并更新。

void pushdown(int x){
    if(!tr[x].tag)return ;
    swap(tr[x].l,tr[x].r);//旋转子树
    tr[tr[x].l].tag^=1;
    tr[tr[x].r].tag^=1;//考虑旋转的性质传递tag,即奇数次翻转->要翻转.偶数次翻转->不需要翻转
    tr[p].tag=0;
}

那么我们就会问了，这样写和线段树有什么区别呢？实际上，有一些旋转的题目确实可以用线段树做。我们考察线段树与平衡时的区别：平衡树的节点上存储的是数组中的一个值，而线段树存储的是一个区间的信息。

分裂

在平衡树模板中，我们按照当前节点的权值来进行分裂。而在文艺平衡树中，我们按照其排名来分裂。为什么呢？因为我们的文艺平衡树维护的是区间的翻转，区间对应着数组中的下标，而下标对应着每个点的排名。注意这里的排名不是值的大小排名，而是对平衡树进行中序遍历的排名。

void split(int i,int k,int &x,int &y){//i当前节点，v划分数值， 返回时x会指向左treap的根，y指向右treap的根
    if(!i){//到达树叶 
        x=y=0;return ;
     }

     pushdown(i);
     if(tr[tr[i].l].size<k){//如果这个点的val<=v,那么它的左子树一定都<=v,但是右子树的root虽然>v,但我们不知道它的儿子们是否都>v,所以需要递归右子树 
        k-=tr[tr[i].l].size+1;//走右子树,那么就要把排名减去左子树的大小.记得更新k
         x=i;
        split(tr[i].r,k,tr[i].r,y);//递归实现 
     }else{
        y=i;
        split(tr[i].l,k,x,tr[i].l);
     }
    pushup(i);
}

合并

加上pushdown即可。

int merge(int x,int y){// x,y分别是左右treap的根 
    if(!x||!y){
        return x+y;
    } 
    if(tr[x].key<tr[y].key){//如果x的key<y的key,那么y就作为x的子树,且是右子树,递归合并x原来的右子树和y
         pushdown(x);
        tr[x].r=merge(tr[x].r,y);
        pushup(x);return x;
    }else{
        pushdown(y);
        tr[y].l=merge(x,tr[y].l);
        pushup(y);return y;
    }
}

输出

用平衡树维护数组，输出应该使用中序遍历

void oup(int x){
    //中序遍历来输出
    if(!x)return ;
    pushdown(x);//注意先下传标记，和线段树的query一样
    oup(tr[x].l);
    cout<<tr[x].val<<' ';
    oup(tr[x].r);
}

操作 main()

        cin>>l>>r;

        split(rt,r,x,z);//分裂为[1,r][r+1,n],根节点分别为x,z
        split(x,l-1,x,y);//把[1,r]分裂为[1,l-1][l,r],根节点分别为x,y
        //那么现在y子树就是[l,r]啦
        tr[y].tag^=1;//注意不是=1
        rt=merge(merge(x,y),z);

Code

/*////////ACACACACACACAC///////////
Code By Ntsc
文艺平衡树
/*////////ACACACACACACAC///////////
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=1e5+5; 

struct node{
    int l,r,val,key,size,tag;
}tr[N];
int n,m,root,idx;  //root记录根的编号 ，idx是对新的节点进行编号的变量 

int addnode(int v){
    tr[++idx].val=v;
    tr[idx].key=rand();
    tr[idx].size=1;
    return idx;//返回这个点在数组里的序号 
} 
void pushup(int i){//向上更新子树大小 
    tr[i].size=tr[tr[i].l].size+tr[tr[i].r].size+1; 
}

void pushdown(int x){
    if(!tr[x].tag)return ;
    swap(tr[x].l,tr[x].r);//旋转子树
    tr[tr[x].l].tag^=1;
    tr[tr[x].r].tag^=1;//考虑旋转的性质传递tag,即奇数次翻转->要翻转.偶数次翻转->不需要翻转
    tr[x].tag=0;
}
//分裂 根据v将树划分为2个子树 
void split(int i,int k,int &x,int &y){//i当前节点，v划分数值， 返回时x会指向左treap的根，y指向右treap的根
    if(!i){//到达树叶 
        x=y=0;return ;
     }

     pushdown(i);
     if(tr[tr[i].l].size<k){//如果这个点的val<=v,那么它的左子树一定都<=v,但是右子树的root虽然>v,但我们不知道它的儿子们是否都>v,所以需要递归右子树 
        k-=tr[tr[i].l].size+1;//走右子树,那么就要把排名减去左子树的大小.记得更新k
         x=i;
        split(tr[i].r,k,tr[i].r,y);//递归实现 
     }else{
        y=i;
        split(tr[i].l,k,x,tr[i].l);
     }
    pushup(i);
}
//合并 分裂的逆过程.递归缝合2个分裂的treap 
int merge(int x,int y){// x,y分别是左右treap的根 
    if(!x||!y){
        return x+y;
    } 
    if(tr[x].key<tr[y].key){//如果x的key<y的key,那么y就作为x的子树,且是右子树,递归合并x原来的右子树和y
         pushdown(x);
        tr[x].r=merge(tr[x].r,y);
        pushup(x);return x;
    }else{
        pushdown(y);
        tr[y].l=merge(x,tr[y].l);
        pushup(y);return y;
    }
}
void insert(int v){
    int x,y,z;
    split(root,v,x,y);
    z=addnode(v);
    root=merge(merge(x,z),y);//相当于z是一个1个节点的树,把它先和x合并(因为x的val均<=v,保证了它的大小顺序,至于它会被放在x的根或者其他地方,凭借key来确定),再和y合并 
}
void del(int v){
    int x,y,z;//将来会分别指向3棵树,他们的节点val分别是<v,=v,>v 
    split(root,v,x,z);//此时分成了2棵树,x指向的树是<=v的,y则是>v的 
    split(x,v-1,x,y);//再把x分成2棵树,把<v(x)的和=v(y)的拎出来 
    y=merge(tr[y].l,tr[y].r);//把y变成y的左右子树合并,相当于把根抛弃了 
    root=merge(merge(x,y),z);//重新合并  
} 
int getk(int i,int k){//获取中序排序第k个值的编号 
    if(k<=tr[tr[i].l].size)return getk(tr[i].l,k);//说明要找到点在左子树,那么去左子树找第k个 
    if(k==tr[tr[i].l].size+1)return i;//找到了 
    return getk(tr[i].r,k-tr[tr[i].l].size-1);//否则 说明要找到点在右子树,那么去左子树找第(k-size左子树)个(左子树已经有size个了,那么要找整个的第k个,只要找右子树的第(k-size左子树)个即可) 
} 
int getpre(int v){//找到v的前驱 (即<v的最大的那个点)
    int x,y;//x,y只是暂时存放一下劈开的2个子树的根,后面还要合并 
    split(root,v-1,x,y);//劈开,变成<v(x)和>=v(y) 2个树 
    int p=getk(x,tr[x].size);//在子树x里面找到最后一个就是 <v(x)的最大的那个点
    cout<<tr[p].val<<endl;
    root=merge(x,y);//别忘了合并 
}   
int getsuc(int v){//找到v的后驱 (即>v的最小的那个点)
    int x,y;
    split(root,v,x,y);//劈开,变成<=v(x)和>v(y) 2个树 
    int p=getk(y,1);//在子树y里面找到第一个就是 >v(x)的最小的那个点
    cout<<tr[p].val<<endl;//cout<<"OK";
    root=merge(x,y);//别忘了合并 
}   
void getrank(int v){//查询val=v的点的排名(从小到大) 如果有重复的val=v的节点只计第一个,排序不去重 
    int x,y;
    split(root,v-1,x,y);//劈开,变成<v(x)和>=v(y) 2个树 
    cout<<tr[x].size+1<<endl;//子树x的大小就是val=v的点前面有几个点 
    root=merge(x,y);
}
void getval(int k){//查询排名为k的节点的值
    int p=getk(root,k);
    cout<<tr[p].val<<endl;

}

void oup(int x){
    //中序遍历来输出
    if(!x)return ;
    pushdown(x);
    oup(tr[x].l);
    cout<<tr[x].val<<' ';
    oup(tr[x].r);
}


signed main(){
    cin>>n>>m;

    for(int i=1;i<=n;i++){
        root=merge(root,addnode(i));
    }
    for(int i=1;i<=m;i++){
        int l,r;
        int x,y,z;
        cin>>l>>r;

        split(root,r,x,z);//分裂为[1,r][r+1,n],根节点分别为x,z
        split(x,l-1,x,y);//把[1,r]分裂为[1,l-1][l,r],根节点分别为x,y
        //那么现在y子树就是[l,r]啦
        tr[y].tag^=1;//注意不是=1
        root=merge(merge(x,y),z);
    }

    oup(root);
    return 0;
}

变形：区间修改平衡树

写一个支持区间加的平衡树

练习 | 这人怎么天天刷题啊（old） Hitchhiking in the Baltic States

/*////////ACACACACACACAC///////////
Code By Ntsc
文艺平衡树改
/*////////ACACACACACACAC///////////

void pushdown(int x){
    if(!tr[x].tag)return ;
    tr[tr[x].l].val+=tr[x].tag;
    tr[tr[x].r].val+=tr[x].tag;
    tr[tr[x].l].tag+=tr[x].tag;
    tr[tr[x].r].tag+=tr[x].tag;//考虑旋转的性质传递tag,即奇数次翻转->要翻转.偶数次翻转->不需要翻转
    tr[x].tag=0;
}
void changeadd(int l,int r,int v){
    int x,y,z;

    split(root,r,x,z);//分裂为[1,r][r+1,n],根节点分别为x,z
    split(x,l-1,x,y);//把[1,r]分裂为[1,l-1][l,r],根节点分别为x,y
    //那么现在y子树就是[l,r]啦
    tr[y].tag+=v;
    tr[y].val+=v;
    root=merge(merge(x,y),z);
}