Treap学习笔记
一、Treap(有旋)
(一)前置知识:
- 前驱:当前序列中小于目标数字的数的最大值
- 后继:当前序列中大于目标数字的数的最小值
- 二叉搜索树BST
(二)变量定义:
ch[u][2]表示第u个节点的两个子节点，其中ch[u][0]表示左子节点,ch[u][1]表示右子节点;- 解释如下的注释
struct Node
{
int val;//每个节点的值
int cnt;//当前节点上存在数值相等的值的个数
int siz;//以自己(包括自己)为根的树上的节点所存储的值的个数之和(即所有cnt之和)
int pri;//优先级，这里我们构建的是一个小根堆
}t[N];
n表示操作数len表示当前节点个数root表示当前的根节点(注意根节点会随节点的变化而发生改变)
(三)各种操作:
操作一:Insert()[插入新节点函数]
void Insert(int &p,int v)//p采取引用是为了方便修改和确定新的根节点
{
if(!p)//走到一个未被定义的节点
{
p=create_node(v);//节点定义函数,下文中介绍
return;
}
if(t[p].val==v)//在平衡树中存在这个新加入的值，直接累加个数即可
{
t[p].siz++;
t[p].cnt++;
return;
}
int d=t[p].val<v;//判断应加入哪个子树，巧妙的判断方法
Insert(ch[p][d],v);
pushup(p);//更新节点siz的函数
if(t[ch[p][d]].pri<t[p].pri)rotate(p,d);//维护其Heap的性质进行旋转,这里采用小根堆
}
操作二:create_node()[节点定义函数]
inline int create_node(int p)
{
t[++len].val=p;
t[len].siz=t[len].cnt=1;
t[len].pri=rand()%1000007;//随机生成优先级
return len;
}
操作三:pushup()[上传size函数]
inline void pushup(int p)
{
t[p].siz=t[ch[p][0]].siz+t[ch[p][1]].siz+t[p].cnt;//左子树+右子树+当前节点
}
操作四:rotate()[旋转函数]
inline void rotate(int &p,int d)//d==0->Zig右旋;d==1->Zag左旋;d表示操作中心的子树(左/右),p是操作的根节点
{
int x=ch[p][d];//暂存p的子节点
ch[p][d]=ch[x][d^1];//将p的子节点的另外一个子节点指向p
ch[x][d^1]=p;//将p的儿子换到根的位置上
t[x].siz=t[p].siz;pushup(p);//处理新的平衡树的size
p=x;//更新根节点的编号
}
操作五:del()[删除节点函数]
bool del(int &p,int x)//删除值为x的节点,true表示已删除,false表示未删除
{
if(!p)return false;//没有这个节点,无法删除
if(x==t[p].val)
{
if(t[p].cnt>1)//存在1个以上以数值等于x的节点,减去一个即可
{
t[p].cnt--;
t[p].siz--;
return true;
}
if(ch[p][0]==0)//没有左子树，它是链节点
{
p=ch[p][1];return true;//将其右子树直接接到父节点上
}
if(ch[p][1]==0)//没有右子树，它是链节点
{
p=ch[p][0];return true;//将其左子树直接接到父节点上
}
if(t[ch[p][0]].pri<t[ch[p][1]].pri)//在不改变优先级的情况下进行旋转，使当前节点成为可操作的链节点后删除
{
rotate(p,0);t[p].siz--;//右旋
return del(ch[p][1],x);//在右子树中删除
}
else
{
rotate(p,1);t[p].siz--;//左旋
return del(ch[p][0],x);//在左子树中删除
}
}
if(!del(ch[p][x<t[p].val?0:1],x))return false;//判断当前值在那棵子树中，并进行删除
t[p].siz--;return true;
}
操作六:query_kth()[查找第k大的数]
int query_kth(int p,int x)
{
if(!p)return 0;
int res=t[ch[p][0]].siz;//res存左子树的大小
if(res<x&&res+t[p].cnt>=x)return t[p].val;//如果数值在当前节点范围内
if(x<=res)return query_kth(ch[p][0],x);//如果x在左子树中
return query_kth(ch[p][1],x-res-t[p].cnt);//如果x在右子树中
}
操作七:query_rank()[查找数值为x的数的排名]
int query_rank(int p,int x)
{
if(!p)return 0;
int res=t[ch[p][0]].siz;//res存左子树的大小
if(x==t[p].val)return res+1;//找到了返回当前排名
if(x<t[p].val)return query_rank(ch[p][0],x);//该数在左子树中
return query_rank(ch[p][1],x)+res+t[p].cnt;//该数在右子树中
}
操作八:query_pre()[查找x的前驱]
int query_pre(int p,int x)
{
if(!p)return -INF;//不存在，返回极小值
if(x<=t[p].val)return query_pre(ch[p][0],x);//前驱在左子树中
int res=query_pre(ch[p][1],x);//前驱在右子树中或当前节点
return max(t[p].val,res);//比较得出前驱
}
操作九:query_sur()[查找x的后继]
int query_sur(int p,int x)
{
if(!p)return INF;//不存在，返回极大值
if(x>=t[p].val)return query_sur(ch[p][1],x);//后继在左子树中
int res=query_sur(ch[p][0],x);//后继在左子树中或当前节点
return min(res,t[p].val);//比较得出后继
}
(四)完整代码:
#include<bits/stdc++.h>
#define init read()
using namespace std;
const int N=10000005;
const int INF=0x7f7f7f7f;
int n,len=0,root=0;
int ch[N][2];
struct Node
{
int val;
int cnt;
int siz;
int pri;
}t[N];
inline int read()
{
int mmm=0,ff=1;char xx=getchar();
while((xx<'0'||xx>'9')&&xx!='-')xx=getchar();
if(xx=='-')ff=-1,xx=getchar();
while(xx>='0'&&xx<='9')
mmm=mmm*10+xx-'0',xx=getchar();
return mmm*ff;
}
inline int create_node(int p)
{
t[++len].val=p;
t[len].siz=t[len].cnt=1;
t[len].pri=rand()%1000007;
return len;
}
inline void pushup(int p)
{
t[p].siz=t[ch[p][0]].siz+t[ch[p][1]].siz+t[p].cnt;
}
inline void rotate(int &p,int d)
{
int x=ch[p][d];
ch[p][d]=ch[x][d^1];
ch[x][d^1]=p;
t[x].siz=t[p].siz;pushup(p);
p=x;
}
void Insert(int &p,int v)
{
if(!p)
{
p=create_node(v);
return;
}
if(t[p].val==v)
{
t[p].siz++;
t[p].cnt++;
return;
}
int d=t[p].val<v;
Insert(ch[p][d],v);
pushup(p);
if(t[ch[p][d]].pri<t[p].pri)rotate(p,d);
}
bool del(int &p,int x)
{
if(!p)return false;
if(x==t[p].val)
{
if(t[p].cnt>1)
{
t[p].cnt--;
t[p].siz--;
return true;
}
if(ch[p][0]==0)
{
p=ch[p][1];return true;
}
if(ch[p][1]==0)
{
p=ch[p][0];return true;
}
if(t[ch[p][0]].pri<t[ch[p][1]].pri)
{
rotate(p,0);t[p].siz--;
return del(ch[p][1],x);
}
else
{
rotate(p,1);t[p].siz--;
return del(ch[p][0],x);
}
}
if(!del(ch[p][x<t[p].val?0:1],x))return false;
t[p].siz--;return true;
}
int query_kth(int p,int x)
{
if(!p)return 0;
int res=t[ch[p][0]].siz;
if(res<x&&res+t[p].cnt>=x)return t[p].val;
if(x<=res)return query_kth(ch[p][0],x);
return query_kth(ch[p][1],x-res-t[p].cnt);
}
int query_rank(int p,int x)
{
if(!p)return 0;
int res=t[ch[p][0]].siz;
if(x==t[p].val)return res+1;
if(x<t[p].val)return query_rank(ch[p][0],x);
return query_rank(ch[p][1],x)+res+t[p].cnt;
}
int query_pre(int p,int x)
{
if(!p)return -INF;
if(x<=t[p].val)return query_pre(ch[p][0],x);
int res=query_pre(ch[p][1],x);
return max(t[p].val,res);
}
int query_sur(int p,int x)
{
if(!p)return INF;
if(x>=t[p].val)return query_sur(ch[p][1],x);
int res=query_sur(ch[p][0],x);
return min(res,t[p].val);
}
int main()
{
freopen("A2128(Treap有旋).in","r",stdin);
freopen("A2128(Treap有旋).out","w",stdout);
srand(unsigned(time(0)));
n=init;
for(int i=1;i<=n;i++)
{
int op=init;
if(op==1)
{
int x=init;
Insert(root,x);
}
else if(op==2)
{
int x=init;
del(root,x);
}
else if(op==3)
{
int x=init;
printf("%d\n",query_rank(root,x));
}
else if(op==4)
{
int x=init;
printf("%d\n",query_kth(root,x));
}
else if(op==5)
{
int x=init;
printf("%d\n",query_pre(root,x));
}
else if(op==6)
{
int x=init;
printf("%d\n",query_sur(root,x));
}
}
return 0;
}
二、FHQ-Treap(非旋)[基础]
(一)前置知识:
(二)变量定义:
ch[u][2]表示第u个节点的两个子节点，其中ch[u][0]表示左子节点,ch[u][1]表示右子节点;- 解释如下的注释
struct Node
{
int val;//每个节点的值
int cnt;//当前节点上存在数值相等的值的个数
int siz;//以自己(包括自己)为根的树上的节点所存储的值的个数之和(即所有cnt之和)
int pri;//优先级，这里我们构建的是一个小根堆
}t[N];
n表示操作数len表示当前节点个数root表示当前的根节点(注意根节点会随节点的变化而发生改变)
(三)各种操作:
操作一:Insert()[插入新节点函数]
void Insert(int &p,int v)
{
if(!p)//不存在这个节点，新建一个
{
p=create_node(v);//新建节点函数
return;
}
int k=query_rank(p,v);//求x的排名，根据排名进行分裂和合并(也可以根据数值,详见“辅助理解”)
int a,b,c;//将原Treap分裂，裂成三颗Treap
//a表示排名比k小的子树(左子树),b表示排名为k的子树(节点),c表示排名比k大的子树(右子树)
split(p,k,a,c);//分裂函数详情见下文
split(a,k-1,a,b);
if(t[b].val==v)//如果存在值相等的节点
{
t[b].cnt++;pushup(b);//直接加节点的cnt
p=merge(a,merge(b,c));//合并函数,详情见下文
}
else
{
p=merge(a,merge(b,create_node(v)));//没有值相等的节点，新建一个并合并
p=merge(p,c);//合并并处理新的根节点
}
}
操作二:create_node()[节点定义函数]
inline int create_node(int p)
{
t[++len].val=p;
t[len].siz=t[len].cnt=1;
t[len].pri=rand()%1000007;//随机生成优先级
return len;
}
操作三:pushup()[上传size函数]
inline void pushup(int p)
{
t[p].siz=t[ch[p][0]].siz+t[ch[p][1]].siz+t[p].cnt;//左子树+右子树+当前节点
}
操作四:split()[分裂函数]
void split(int p,int k,int &l,int &r)//p表示当前Treap的根节点,k表示所查询的排名，l表示左子树，r表示右子树
{
if(!p)//如果该子树为空，执行断开操作
{
l=r=0;
return;
}
if(t[ch[p][0]].siz>=k)//如果排名为k的节点在左子树中
{
r=p;//将当前节点划入右子树中
split(ch[p][0],k,l,ch[p][0]);//在左子树中找点
}
else//如果排名为k的节点在右子树中
{
l=p;//将当前节点划入左子树中
split(ch[p][1],k-t[ch[p][0]].siz-t[p].cnt,ch[p][1],r);//在右子树中找点
}
pushup(p);//上传
}
操作五:merge()[合并函数]
int merge(int a,int b)//a表示左子树的根节点;b表示右子树的根节点(有顺序性!)，返回根节点的编号
{
if(!a||!b)return a+b;//返回有值的节点作为根节点
int x;
if(t[a].pri<t[b].pri)//如果左子树的优先级低于右子树
{
x=a;//将优先级小的a作为根节点
ch[x][1]=merge(ch[x][1],b);//处理其右子树
}
else
{
x=b;//将优先级小的b作为根节点
ch[x][0]=merge(a,ch[x][0]);//处理其左子树
}
pushup(x);//上传
return x;//返回根节点
}
操作六:del()[删除节点函数]
void del(int x)//删除值为x的节点
{
int k=query_rank(root,x);//得到值为x的编号
int a,b,c;//这几行和Insert()函数里的意思是一样的
split(root,k,a,c);
split(a,k-1,a,b);
if(t[b].cnt>1)//如果等于该值的节点数不止一个直接cnt-1即可
{
t[b].cnt--;pushup(b);
root=merge(a,merge(b,c));//合并刚才分开的Treap
}
else root=merge(a,c);//如果等于该值的节点数只有一个，删除它(即直接合并a和c)
}
操作七:query_kth()[查找第k大的数]
int query_kth(int p,int x)
{
if(!p)return 0;
int res=t[ch[p][0]].siz;//res存左子树的大小
if(res<x&&res+t[p].cnt>=x)return t[p].val;//如果数值在当前节点范围内
if(x<=res)return query_kth(ch[p][0],x);//如果x在左子树中
return query_kth(ch[p][1],x-res-t[p].cnt);//如果x在右子树中
}
操作八:query_rank()[查找数值为x的数的排名]
int query_rank(int p,int x)
{
if(!p)return 0;
int res=t[ch[p][0]].siz;//res存左子树的大小
if(x==t[p].val)return res+1;//找到了返回当前排名
if(x<t[p].val)return query_rank(ch[p][0],x);//该数在左子树中
return query_rank(ch[p][1],x)+res+t[p].cnt;//该数在右子树中
}
操作九:query_pre()[查找x的前驱]
int query_pre(int p,int x)
{
if(!p)return -INF;//不存在，返回极小值
if(x<=t[p].val)return query_pre(ch[p][0],x);//前驱在左子树中
int res=query_pre(ch[p][1],x);//前驱在右子树中或当前节点
return max(t[p].val,res);//比较得出前驱
}
操作十:query_sur()[查找x的后继]
int query_sur(int p,int x)
{
if(!p)return INF;//不存在，返回极大值
if(x>=t[p].val)return query_sur(ch[p][1],x);//后继在左子树中
int res=query_sur(ch[p][0],x);//后继在左子树中或当前节点
return min(res,t[p].val);//比较得出后继
}
(四)完整代码:
#include<bits/stdc++.h>
#define init read()
using namespace std;
const int N=10000005;
const int INF=0x7f7f7f7f;
int n,len=0,root=0;
int ch[N][2];
struct Node
{
int val;
int cnt;
int siz;
int pri;
}t[N];
inline int read()
{
int mmm=0,ff=1;char xx=getchar();
while((xx<'0'||xx>'9')&&xx!='-')xx=getchar();
if(xx=='-')ff=-1,xx=getchar();
while(xx>='0'&&xx<='9')
mmm=mmm*10+xx-'0',xx=getchar();
return mmm*ff;
}
inline void pushup(int p)
{
t[p].siz=t[ch[p][0]].siz+t[ch[p][1]].siz+t[p].cnt;
}
inline int create_node(int x)
{
t[++len].val=x;
t[len].siz=t[len].cnt=1;
t[len].pri=rand()%1000007;
return len;
}
int merge(int a,int b)//a表示左子树的根节点 b表示右子树的根节点(有顺序性!)
{
if(!a||!b)return a+b;
int x;
if(t[a].pri<t[b].pri)
{
x=a;
ch[x][1]=merge(ch[x][1],b);
}
else
{
x=b;
ch[x][0]=merge(a,ch[x][0]);
}
pushup(x);
return x;
}
void split(int p,int k,int &l,int &r)
{
if(!p)
{
l=r=0;
return;
}
if(t[ch[p][0]].siz>=k)
{
r=p;
split(ch[p][0],k,l,ch[p][0]);
}
else
{
l=p;
split(ch[p][1],k-t[ch[p][0]].siz-t[p].cnt,ch[p][1],r);
}
pushup(p);
}
int query_kth(int p,int x)
{
if(!p)return 0;
int res=t[ch[p][0]].siz;
if(res<x&&res+t[p].cnt>=x)return t[p].val;
if(x<=res)return query_kth(ch[p][0],x);
return query_kth(ch[p][1],x-res-t[p].cnt);
}
int query_rank(int p,int x)
{
if(!p)return 0;
int res=t[ch[p][0]].siz;
if(x==t[p].val)return res+1;
if(x<t[p].val)return query_rank(ch[p][0],x);
return query_rank(ch[p][1],x)+res+t[p].cnt;
}
int query_pre(int p,int x)
{
if(!p)return -INF;
if(x<=t[p].val)return query_pre(ch[p][0],x);
int res=query_pre(ch[p][1],x);
return max(t[p].val,res);
}
int query_sur(int p,int x)
{
if(!p)return INF;
if(x>=t[p].val)return query_sur(ch[p][1],x);
int res=query_sur(ch[p][0],x);
return min(res,t[p].val);
}
void Insert(int &p,int v)
{
if(!p)
{
p=create_node(v);
return;
}
int k=query_rank(p,v);
int a,b,c;
split(p,k,a,c);
split(a,k-1,a,b);
if(t[b].val==v)
{
t[b].cnt++;pushup(b);//merge时必须满足顺序性!!!
p=merge(a,merge(b,c));
}
else
{
p=merge(a,merge(b,create_node(v)));
p=merge(p,c);
}
}
void del(int x)
{
int k=query_rank(root,x);
int a,b,c;
split(root,k,a,c);
split(a,k-1,a,b);
if(t[b].cnt>1)
{
t[b].cnt--;pushup(b);
root=merge(a,merge(b,c));
}
else root=merge(a,c);
}
int main()
{
freopen("A2128(FHQ-Treap非旋).in","r",stdin);
freopen("A2128(FHQ-Treap非旋).out","w",stdout);
srand(unsigned(time(0)));
n=init;
for(int i=1;i<=n;i++)
{
int op=init;
if(op==1)
{
int x=init;
Insert(root,x);
}
else if(op==2)
{
int x=init;
del(x);
}
else if(op==3)
{
int x=init;
printf("%d\n",query_rank(root,x));
}
else if(op==4)
{
int x=init;
printf("%d\n",query_kth(root,x));
}
else if(op==5)
{
int x=init;
printf("%d\n",query_pre(root,x));
}
else if(op==6)
{
int x=init;
printf("%d\n",query_sur(root,x));
}
}
return 0;
}
三、FHQ-Treap(非旋)[区间翻转]
(一)典型例题及思路点拨-文艺平衡树
本题没有Insert()函数，并且其并不满足BST的性质，我们只是需要保持它的平衡和顺序性。把每个节点作为上一个节点的右子节点保证了中序遍历的顺序性，同时它又具有平衡性，故时间复杂度为O(nlogn)。每次的翻转操作是把其左右子节点进行交换并打上标记(注意此时的子树是已被split()函数分离出来了的)，故交换不影响全局。
接下来对这样交换一定是翻转进行证明：中序遍历的顺序为:左子树->根->右子树，从上到下交换所有左右子节点后中遍历顺序变为:原右子树->根->原左子树。交换前后的两棵树成镜像，故此时的中序遍历的结果是翻转后的结果，证毕。
补充练习NOI2005 维护数列
(二)前置知识:
- 非旋Treap基础版
- 辅助理解
(三)变量定义:
ch[u][2]表示第u个节点的两个子节点，其中ch[u][0]表示左子节点,ch[u][1]表示右子节点;- 解释如下的注释
struct Node
{
int val;//每个节点的值
int siz;//以自己(包括自己)为根的树上的节点个数之和
int pri;//优先级，这里我们构建的是一个小根堆
bool lazy;//懒惰标记表示这个区间要进行翻转
}t[N];
n表示数字个数len表示当前节点个数root表示当前的根节点(注意根节点会随节点的变化而发生改变)m表示操作个数
(四)各种操作:
操作一:create_node()[节点定义函数]
inline int create_node(int x)
{
t[++len].val=x;
t[len].siz=1;
t[len].pri=rand()%1000007;
t[len].lazy=false;//一开始不翻转记录为false
return len;
}
操作二:pushup()[长度上传函数]
inline void pushup(int p)
{
t[p].siz=t[ch[p][0]].siz+t[ch[p][1]].siz+1;//处理Treap的大小(不可能存在同一个值的节点)
}
操作三:pushdown()[标记下传函数]
inline void pushdown(int p)
{
if(t[p].lazy)//如果不用翻转就返回即可
{
swap(ch[p][0],ch[p][1]);//翻转两个子节点
t[ch[p][0]].lazy^=1;//为何可以这么翻转详见“辅助理解”和思路点拨
t[ch[p][1]].lazy^=1;
t[p].lazy=false;//取消标记
}
return;
}
操作四:split()[分离要被翻转的Treap函数]
void split(int p,int k,int &l,int &r)//当前位置为p，分离前k个数(包括第k个)，l表示分离出来的树(左子树)的根节点，r表示剩下的树(右子树)的根节点
{
if(!p)//不存在这个节点返回0
{
l=r=0;
return;
}
pushdown(p);//在分离前下传标记，不然标记会下传不完全或者传错
if(t[ch[p][0]].siz<k)//如果目标k在右子树中
{
l=p;//p即为分离出来的树的根节点，更新
split(ch[p][1],k-t[ch[p][0]].siz-1,ch[p][1],r);//处理剩下的树的根节点
}
else
{
r=p;//p即为剩下的树的根节点，更新
split(ch[p][0],k,l,ch[p][0]);//处理分离出来的树的根节点
}
pushup(p);//上传长度
}
操作五:merge()[合并子树函数]
int merge(int l,int r)
{
if(!l||!r)return l+r;
int x;//x存储根节点的编号
if(t[l].pri<t[r].pri)//保证优先级小的在上方
{
x=l;pushdown(x);//根节点是l，先下传后合并，不然标记会下传不完全或者传错
ch[l][1]=merge(ch[l][1],r);//把l的右子树和以r为根的树合并
}
else
{
x=r;pushdown(x);//根节点是r，下传
ch[r][0]=merge(l,ch[r][0]);//把r的左子树和以l为根的树合并
}
pushup(x);//上传
return x;
}
操作六:write()[输出中序遍历函数]
void write(int u)
{
if(u==0)return;//不存在这个节点返回
if(t[u].lazy)pushdown(u);//把未下传的标记下传
write(ch[u][0]);//先输出左子树
printf("%d ",u);//再输出根节点
write(ch[u][1]);//最后输出右子树
}
(五)完整代码:
#include<bits/stdc++.h>
#define init read()
using namespace std;
const int N=100005;
int n,m,root,len;
int ch[N][2];
struct Node
{
int siz;
int pri;
int val;
bool lazy;
}t[N];
inline int read()
{
int mmm=0,ff=1;char xx=getchar();
while((xx<'0'||xx>'9')&&xx!='-')xx=getchar();
if(xx=='-')ff=-1,xx=getchar();
while(xx>='0'&&xx<='9')
mmm=mmm*10+xx-'0',xx=getchar();
return mmm*ff;
}
inline int create_node(int x)
{
t[++len].val=x;
t[len].siz=1;
t[len].pri=rand()%1000007;
t[len].lazy=false;
return len;
}
inline void pushup(int p)
{
t[p].siz=t[ch[p][0]].siz+t[ch[p][1]].siz+1;
}
inline void pushdown(int p)
{
if(t[p].lazy)
{
swap(ch[p][0],ch[p][1]);
t[ch[p][0]].lazy^=1;
t[ch[p][1]].lazy^=1;
t[p].lazy=false;
}
return;
}
void split(int p,int k,int &l,int &r)
{
if(!p)
{
l=r=0;
return;
}
pushdown(p);
if(t[ch[p][0]].siz<k)
{
l=p;
split(ch[p][1],k-t[ch[p][0]].siz-1,ch[p][1],r);
}
else
{
r=p;
split(ch[p][0],k,l,ch[p][0]);
}
pushup(p);
}
int merge(int l,int r)
{
if(!l||!r)return l+r;
int x;
if(t[l].pri<t[r].pri)
{
x=l;pushdown(x);
ch[l][1]=merge(ch[l][1],r);
}
else
{
x=r;pushdown(x);
ch[r][0]=merge(l,ch[r][0]);
}
pushup(x);
return x;
}
void write(int u)
{
if(u==0)return;
if(t[u].lazy)pushdown(u);
write(ch[u][0]);
printf("%d ",u);
write(ch[u][1]);
}
int main()
{
freopen("A2130(非旋Treap-文艺平衡树).in","r",stdin);
freopen("A2130(非旋Treap-文艺平衡树).out","w",stdout);
n=init;m=init;
for(int i=1;i<=n;i++)
{
root=merge(root,create_node(i));
}
for(int i=1;i<=m;i++)
{
int a,b,c;
int l=init,r=init;
split(root,l-1,a,b);
split(b,r-l+1,b,c);
t[b].lazy^=1;
root=merge(a,merge(b,c));
}
write(root);
return 0;
}