struct Splay
{
#define ls(x) t[x].lson
#define rs(x) t[x].rson
#define fa(x) t[x].pre
#define grafa(x) t[t[x].pre].pre
static const int __=200005;
struct node
{
int pre,lson,rson;
ll val,minn,ad;
int siz,rev;
void set(int p,int v,int s)
{
val=minn=v,siz=s;
pre=p,lson=-1,rson=-1,
ad=0,rev=0;
}
void operator+=(const node &b)
{
siz+=b.siz;
minn=min(minn,b.minn);
}
void putrev(){rev^=1;}
void putadd(ll v)
{
val+=v,minn+=v,ad+=v;
}
}t[__];
int root,idx;
Splay():root(0),idx(0){t[0].set(-1,0,0);}
void build(int a[],int n)
{
rs(0)=build(0,a,1,n);
}
int build(int pre,int a[],int l,int r)
{
if(l>r)return -1;
int m=(l+r)>>1,x=++idx;
t[x].set(pre,a[m],1);
ls(x)=build(x,a,l,m-1);
rs(x)=build(x,a,m+1,r);
if(~ls(x))t[x]+=t[ls(x)];
if(~rs(x))t[x]+=t[rs(x)];
return x;
}
void pushup(int x)
{
t[x].siz=(x!=0);
t[x].minn=t[x].val;
if(~ls(x))t[x]+=t[ls(x)];
if(~rs(x))t[x]+=t[rs(x)];
}
void zig(int x)
{
int y=fa(x);
if(~fa(y))
if(ls(fa(y))==y)
ls(fa(y))=x;
else rs(fa(y))=x;
fa(x)=fa(y),fa(y)=x;
ls(y)=rs(x);
if(~ls(y))fa(ls(y))=y;
rs(x)=y;
if(fa(x)==-1)root=x;
pushup(y),pushup(x);
}
void zag(int x)
{
int y=fa(x);
if(~fa(y))
if(ls(fa(y))==y)
ls(fa(y))=x;
else rs(fa(y))=x;
fa(x)=fa(y),fa(y)=x;
rs(y)=ls(x);
if(~rs(y))fa(rs(y))=y;
ls(x)=y;
if(fa(x)==-1)root=x;
pushup(y),pushup(x);
}
void splay(int x,int wz=-1)
{
while(x!=wz && fa(x)!=wz)
if(grafa(x)==wz)
if(ls(fa(x))==x)zig(x);
else zag(x);
else if(ls(fa(x))==x && ls(grafa(x))==fa(x))
zig(fa(x)),zig(x);
else if(rs(fa(x))==x && rs(grafa(x))==fa(x))
zag(fa(x)),zag(x);
else if(ls(fa(x))==x && rs(grafa(x))==fa(x))
zig(x),zag(x);
else if(rs(fa(x))==x && ls(grafa(x))==fa(x))
zag(x),zig(x);
}
void pushdown(int x)
{
if(t[x].rev)
{
swap(ls(x),rs(x));
if(ls(x)>0)t[ls(x)].putrev();
if(rs(x)>0)t[rs(x)].putrev();
t[x].rev=0;
}
if(t[x].ad)
{
ll &add=t[x].ad;
if(ls(x)>0)t[ls(x)].putadd(add);
if(rs(x)>0)t[rs(x)].putadd(add);
add=0;
}
}
int find_node(int wz)
{
int x=root;
while(~x)
{
pushdown(x);
int k=(x!=0);
if(~ls(x))
k+=t[ls(x)].siz;
if(k==wz)return x;
if(wz<k)x=ls(x);
else wz-=k,x=rs(x);
}
return -1;
}
int get_min(int x)
{
for(pushdown(x);~ls(x);pushdown(x=ls(x)));
return x;
}
//a[wz]后插入一个数val
void insert(int wz,int val)
{
int x=find_node(wz);
splay(x);
if(rs(root)==-1)
{
rs(root)=++idx;
t[idx].set(root,val,1);
return;
}
int y=get_min(rs(root));
splay(y,root);
ls(rs(root))=++idx;
t[idx].set(rs(root),val,1);
pushup(rs(root)),pushup(root);
}
//删除a[wz]
void erase(int wz)
{
int x=find_node(wz);
splay(x);
if(ls(x)==-1 && rs(x)==-1)
root=-1;
else if(ls(x)==-1)
{
root=rs(x),fa(rs(x))=-1;
pushup(root);
}
else if(rs(x)==-1)
{
root=ls(x),fa(ls(x))=-1;
pushup(root);
}
else
{
int y=get_min(rs(x));
fa(ls(x))=y,ls(y)=ls(x);
root=rs(x),fa(rs(x))=-1;
pushup(y),pushup(root);
splay(y);
}
}
//a[l]……a[r] +val
void add(int l,int r,ll val)
{
int le=find_node(l-1);
int ri=find_node(r+1);
splay(le),splay(ri,le);
t[ls(rs(root))].putadd(val);
}
//a[l]……a[r] -> a[r]……a[l]
void reversal(int l,int r)
{
int le=find_node(l-1);
int ri=find_node(r+1);
splay(le),splay(ri,le);
t[ls(rs(root))].putrev();
}
//min(a[l]……a[r])
ll get_min(int l,int r)
{
int le=find_node(l-1);
int ri=find_node(r+1);
splay(le),splay(ri,le);
return t[ls(rs(root))].minn;
}
//a[l]……a[r] -> a[r-k+1]……a[r]a[l]……a[r-k]
void revolve(int l,int r,int k)
{
k=(k%(r-l+1)+(r-l+1))%(r-l+1);
if(!k)return;
int le=find_node(l-1);
int ri=find_node(r-k+1);
splay(le),splay(ri,le);
int x=ls(rs(root));
int y=find_node(r);
ls(rs(root))=-1;
pushup(rs(root)),pushup(root);
splay(y);
int z=get_min(rs(root));
splay(z,root);
ls(rs(root))=x,fa(x)=rs(root);
pushup(rs(root)),pushup(root);
}
void print(){dfs(root);}
void dfs(int x)
{
if(x==-1)return;
dfs(ls(x));
printf("%d: pre:%d ls:%d rs:%d\n",x,fa(x),ls(x),rs(x));
dfs(rs(x));
}
}T;
splay:
#define ls(x) tree[x].lson
#define rs(x) tree[x].rson
#define fa(x) tree[x].pre
#define grafa(x) tree[tree[x].pre].pre
struct node
{
int pre,lson,rson;
int val,cont,siz;
node(int pre=-1,int lson=-1,int rson=-1,
int val=0,int cont=0,int siz=0):
pre(pre),lson(lson),rson(rson),
val(val),cont(cont),siz(siz) {}
} tree[100005];
int root=-1,idx=0;
void pushup(int x)
{
tree[x].siz=tree[x].cont;
if(~ls(x))
tree[x].siz+=tree[ls(x)].siz;
if(~rs(x))
tree[x].siz+=tree[rs(x)].siz;
}
void zig(int x)
{
int y=fa(x);
if(~fa(y))
if(ls(fa(y))==y)
ls(fa(y))=x;
else rs(fa(y))=x;
fa(x)=fa(y),fa(y)=x;
ls(y)=rs(x);
if(~ls(y))fa(ls(y))=y;
rs(x)=y;
if(fa(x)==-1)root=x;
pushup(y),pushup(x);
}
void zag(int x)
{
int y=fa(x);
if(~fa(y))
if(ls(fa(y))==y)
ls(fa(y))=x;
else rs(fa(y))=x;
fa(x)=fa(y),fa(y)=x;
rs(y)=ls(x);
if(~rs(y))fa(rs(y))=y;
ls(x)=y;
if(fa(x)==-1)root=x;
pushup(y),pushup(x);
}
void splay(int x,int wz=-1)
{
while(x!=wz && fa(x)!=wz)
{
if(grafa(x)==wz)
if(ls(fa(x))==x)zig(x);
else zag(x);
else if(ls(fa(x))==x && ls(grafa(x))==fa(x))
zig(fa(x)),zig(x);
else if(rs(fa(x))==x && rs(grafa(x))==fa(x))
zag(fa(x)),zag(x);
else if(ls(fa(x))==x && rs(grafa(x))==fa(x))
zig(x),zag(x);
else if(rs(fa(x))==x && ls(grafa(x))==fa(x))
zag(x),zig(x);
}
}
int get_min(int x)
{
while(~ls(x))x=ls(x);
return x;
}
int get_max(int x)
{
while(~rs(x))x=rs(x);
return x;
}
int find_node(int val)
{
int x=root;
while(~x)
{
if(tree[x].val==val)
{
splay(x);
return x;
}
if(val<tree[x].val)
x=ls(x);
else x=rs(x);
}
return -1;
}
int get_rank(int val)
{
int res=1,x=root;
while(~x)
if(val<tree[x].val)
x=ls(x);
else
{
if(~ls(x))
res+=tree[ls(x)].siz;
if(tree[x].val==val)
{
splay(x);
return res;
}
res+=tree[x].cont;
x=rs(x);
}
return res;
}
int get_kth(int k)
{
int x=root,y=-1;
while(~x)
{
y=x;
if(~ls(x) && k<=tree[ls(x)].siz)
x=ls(x);
else
{
int z=tree[x].cont;
if(~ls(x))
z+=tree[ls(x)].siz;
if(k<=z)break;
k-=z;
x=rs(x);
}
}
splay(y);
return tree[y].val;
}
void insrt(int val)
{
int x=root,y=find_node(val);
if(~y)
{
tree[y].cont++;
tree[y].siz++;
return;
}
while(~x)
{
y=x;
if(val<tree[x].val)
x=ls(x);
else x=rs(x);
}
x=++idx;
tree[x]=node(y,-1,-1,val,1,1);
if(y==-1)root=x;
else
{
if(val<tree[y].val)
ls(y)=x;
else rs(y)=x;
pushup(y),splay(x);
}
}
int smaller(int val)
{
int x=root,y=-1;
while(~x)
{
if(val>tree[x].val && (y==-1 ||
(~y && tree[x].val>tree[y].val)))
y=x;
if(val<=tree[x].val)x=ls(x);
else x=rs(x);
}
splay(y);
return tree[y].val;
}
int bigger(int val)
{
int x=root,y=-1;
while(~x)
{
if(val<tree[x].val && (y==-1 ||
(~y && tree[x].val<tree[y].val)))
y=x;
if(val<tree[x].val)x=ls(x);
else x=rs(x);
}
splay(y);
return tree[y].val;
}
void delet(int val)
{
int x=find_node(val);
if(x==-1)return;
if(tree[x].cont>1)
{
tree[x].cont--;
tree[x].siz--;
return;
}
if(ls(x)==-1 && rs(x)==-1)
root=-1;
else if(ls(x)==-1)
{
root=rs(x),fa(rs(x))=-1;
pushup(root);
}
else if(rs(x)==-1)
{
root=ls(x),fa(ls(x))=-1;
pushup(root);
}
else
{
int y=get_min(rs(x));
fa(ls(x))=y,ls(y)=ls(x);
root=rs(x),fa(rs(x))=-1;
pushup(y),pushup(root);
splay(y);
}
}
int main()
{
int q;
scanf("%d",&q);
while(q--)
{
int op,val;
scanf("%d%d",&op,&val);
if(op==1)insrt(val);
if(op==2)delet(val);
if(op==3)printf("%d\n",get_rank(val));
if(op==4)printf("%d\n",get_kth(val));
if(op==5)printf("%d\n",smaller(val));
if(op==6)printf("%d\n",bigger(val));
}
return 0;
}
区间翻转:
#define ls(x) tree[x].lson
#define rs(x) tree[x].rson
#define fa(x) tree[x].pre
#define grafa(x) tree[tree[x].pre].pre
struct node
{
int pre,lson,rson;
int siz,lazy;
node(int pre=-1,int siz=0):
pre(pre),siz(siz),
lson(-1),rson(-1),lazy(0) {}
} tree[100005];
int root=-1,idx=-1;
void pushup(int x)
{
tree[x].siz=(x!=0);
if(~ls(x))tree[x].siz+=tree[ls(x)].siz;
if(~rs(x))tree[x].siz+=tree[rs(x)].siz;
}
inline void zig(int x)
{
int y=fa(x);
if(~fa(y))
if(ls(fa(y))==y)
ls(fa(y))=x;
else rs(fa(y))=x;
fa(x)=fa(y),fa(y)=x;
ls(y)=rs(x);
if(~ls(y))fa(ls(y))=y;
rs(x)=y;
if(fa(x)==-1)root=x;
pushup(y),pushup(x);
}
inline void zag(int x)
{
int y=fa(x);
if(~fa(y))
if(ls(fa(y))==y)
ls(fa(y))=x;
else rs(fa(y))=x;
fa(x)=fa(y),fa(y)=x;
rs(y)=ls(x);
if(~rs(y))fa(rs(y))=y;
ls(x)=y;
if(fa(x)==-1)root=x;
pushup(y),pushup(x);
}
void splay(int x,int wz=-1)
{
while(x!=wz && fa(x)!=wz)
if(grafa(x)==wz)
if(ls(fa(x))==x)zig(x);
else zag(x);
else if(ls(fa(x))==x && ls(grafa(x))==fa(x))
zig(fa(x)),zig(x);
else if(rs(fa(x))==x && rs(grafa(x))==fa(x))
zag(fa(x)),zag(x);
else if(ls(fa(x))==x && rs(grafa(x))==fa(x))
zig(x),zag(x);
else if(rs(fa(x))==x && ls(grafa(x))==fa(x))
zag(x),zig(x);
}
void insrt(int wz)
{
int x=root,y=-1;
while(~x)
if(wz<tree[y=x].siz)
x=ls(x);
else x=rs(x);
x=++idx;
tree[x]=node(y,1);
if(y==-1)root=x;
else
{
if(wz<tree[y].siz)
ls(y)=x;
else rs(y)=x;
pushup(y),splay(x);
}
}
inline void pushdown(int id)
{
if(!tree[id].lazy)return;
swap(ls(id),rs(id));
tree[id].lazy=0;
if(~ls(id))tree[ls(id)].lazy^=1;
if(~rs(id))tree[rs(id)].lazy^=1;
}
int find_node(int wz)
{
int x=root;
while(~x)
{
pushdown(x);
int k=(x!=0);
if(~ls(x))
k+=tree[ls(x)].siz;
if(k==wz)return x;
if(wz<k)x=ls(x);
else wz-=k,x=rs(x);
}
return -1;
}
inline void reversal(int l,int r)
{
int le=find_node(l-1);
int ri=find_node(r+1);
splay(le);
splay(ri,le);
int x=ls(rs(root));
tree[x].lazy^=1;
}
void dfs(int x,int n)
{
pushdown(x);
if(~ls(x))dfs(ls(x),n);
if(x!=0 && x!=n+1)
printf("%d ",x);
if(~rs(x))dfs(rs(x),n);
}
int main()
{
int n,q;
scanf("%d%d",&n,&q);
for(int i=0; i<=n+1; i++)
insrt(i);
while(q--)
{
int l,r;
scanf("%d%d",&l,&r);
reversal(l,r);
}
dfs(root,n);
return 0;
}
区间翻转/合并:
#define ls(x) tree[x].lson
#define rs(x) tree[x].rson
#define fa(x) tree[x].pre
#define grafa(x) tree[tree[x].pre].pre
struct node
{
int pre,lson,rson;
int siz,lazy;
node(int pre=-1,int siz=0):
pre(pre),siz(siz),
lson(-1),rson(-1),lazy(0) {}
} tree[100005];
int root=-1,idx=-1;
void pushup(int x)
{
tree[x].siz=(x!=0);
if(~ls(x))tree[x].siz+=tree[ls(x)].siz;
if(~rs(x))tree[x].siz+=tree[rs(x)].siz;
}
inline void zig(int x)
{
int y=fa(x);
if(~fa(y))
if(ls(fa(y))==y)
ls(fa(y))=x;
else rs(fa(y))=x;
fa(x)=fa(y),fa(y)=x;
ls(y)=rs(x);
if(~ls(y))fa(ls(y))=y;
rs(x)=y;
if(fa(x)==-1)root=x;
pushup(y),pushup(x);
}
inline void zag(int x)
{
int y=fa(x);
if(~fa(y))
if(ls(fa(y))==y)
ls(fa(y))=x;
else rs(fa(y))=x;
fa(x)=fa(y),fa(y)=x;
rs(y)=ls(x);
if(~rs(y))fa(rs(y))=y;
ls(x)=y;
if(fa(x)==-1)root=x;
pushup(y),pushup(x);
}
void splay(int x,int wz=-1)
{
while(x!=wz && fa(x)!=wz)
if(grafa(x)==wz)
if(ls(fa(x))==x)zig(x);
else zag(x);
else if(ls(fa(x))==x && ls(grafa(x))==fa(x))
zig(fa(x)),zig(x);
else if(rs(fa(x))==x && rs(grafa(x))==fa(x))
zag(fa(x)),zag(x);
else if(ls(fa(x))==x && rs(grafa(x))==fa(x))
zig(x),zag(x);
else if(rs(fa(x))==x && ls(grafa(x))==fa(x))
zag(x),zig(x);
}
void insrt(int wz)
{
int x=root,y=-1;
while(~x)
if(wz<tree[y=x].siz)
x=ls(x);
else x=rs(x);
x=++idx;
tree[x]=node(y,1);
if(y==-1)root=x;
else
{
if(wz<tree[y].siz)
ls(y)=x;
else rs(y)=x;
pushup(y),splay(x);
}
}
inline void pushdown(int id)
{
if(!tree[id].lazy)return;
swap(ls(id),rs(id));
tree[id].lazy=0;
if(~ls(id))tree[ls(id)].lazy^=1;
if(~rs(id))tree[rs(id)].lazy^=1;
}
int find_node(int wz)
{
int x=root;
while(~x)
{
pushdown(x);
int k=(x!=0);
if(~ls(x))
k+=tree[ls(x)].siz;
if(k==wz)return x;
if(wz<k)x=ls(x);
else wz-=k,x=rs(x);
}
return -1;
}
inline void reversal(int l,int r,int n)
{
int le=find_node(l-1);
int ri=find_node(r+1);
splay(le),splay(ri,le);
int x=ls(rs(root));
ls(rs(root))=-1;
pushup(rs(root)),pushup(root);
tree[x].lazy^=1;
int y=find_node(n-r+l-1);
splay(y);
ls(rs(root))=x,fa(x)=rs(root);
pushup(rs(root)),pushup(root);
}
void dfs(int x,int n)
{
pushdown(x);
if(~ls(x))dfs(ls(x),n);
if(x!=0 && x!=n+1)
printf("%d\n",x);
if(~rs(x))dfs(rs(x),n);
}
int main()
{
int n,q;
scanf("%d%d",&n,&q);
for(int i=0;i<=n+1;i++)
insrt(i);
while(q--)
{
int l,r;
scanf("%d%d",&l,&r);
reversal(l,r,n);
}
dfs(root,n);
return 0;
}
区间翻转/合并:
#define ls(x) tree[x].lson
#define rs(x) tree[x].rson
#define fa(x) tree[x].pre
#define grafa(x) tree[tree[x].pre].pre
struct node
{
int pre,lson,rson;
int siz,lazy;
node(int pre=-1,int siz=0):
pre(pre),siz(siz),
lson(-1),rson(-1),lazy(0) {}
} tree[300005];
int root=-1,idx=-1;
void pushup(int x)
{
tree[x].siz=(x!=0);
if(~ls(x))tree[x].siz+=tree[ls(x)].siz;
if(~rs(x))tree[x].siz+=tree[rs(x)].siz;
}
inline void zig(int x)
{
int y=fa(x);
if(~fa(y))
if(ls(fa(y))==y)
ls(fa(y))=x;
else rs(fa(y))=x;
fa(x)=fa(y),fa(y)=x;
ls(y)=rs(x);
if(~ls(y))fa(ls(y))=y;
rs(x)=y;
if(fa(x)==-1)root=x;
pushup(y),pushup(x);
}
inline void zag(int x)
{
int y=fa(x);
if(~fa(y))
if(ls(fa(y))==y)
ls(fa(y))=x;
else rs(fa(y))=x;
fa(x)=fa(y),fa(y)=x;
rs(y)=ls(x);
if(~rs(y))fa(rs(y))=y;
ls(x)=y;
if(fa(x)==-1)root=x;
pushup(y),pushup(x);
}
void splay(int x,int wz=-1)
{
while(x!=wz && fa(x)!=wz)
if(grafa(x)==wz)
if(ls(fa(x))==x)zig(x);
else zag(x);
else if(ls(fa(x))==x && ls(grafa(x))==fa(x))
zig(fa(x)),zig(x);
else if(rs(fa(x))==x && rs(grafa(x))==fa(x))
zag(fa(x)),zag(x);
else if(ls(fa(x))==x && rs(grafa(x))==fa(x))
zig(x),zag(x);
else if(rs(fa(x))==x && ls(grafa(x))==fa(x))
zag(x),zig(x);
}
void insrt(int val)
{
int x=root,y=-1;
while(~x)
if(val<tree[y=x].siz)
x=ls(x);
else x=rs(x);
x=++idx;
tree[x]=node(y,1);
if(y==-1)root=x;
else
{
if(val<tree[y].siz)
ls(y)=x;
else rs(y)=x;
pushup(y),splay(x);
}
}
inline void pushdown(int id)
{
if(!tree[id].lazy)return;
swap(ls(id),rs(id));
tree[id].lazy=0;
if(~ls(id))tree[ls(id)].lazy^=1;
if(~rs(id))tree[rs(id)].lazy^=1;
}
int find_node(int wz)
{
int x=root;
while(~x)
{
pushdown(x);
int k=(x!=0);
if(~ls(x))
k+=tree[ls(x)].siz;
if(k==wz)return x;
if(wz<k)x=ls(x);
else wz-=k,x=rs(x);
}
return -1;
}
inline void flip(int l,int r)
{
int le=find_node(l-1);
int ri=find_node(r+1);
splay(le);
splay(ri,le);
int x=ls(rs(root));
tree[x].lazy^=1;
}
int get_min(int x)
{
pushdown(x);
while(~ls(x))
{
x=ls(x);
pushdown(x);
}
return x;
}
inline void cut(int l,int r,int k)
{
int le=find_node(l-1);
int ri=find_node(r+1);
splay(le),splay(ri,le);
int x=ls(rs(root));
ls(rs(root))=-1;
pushup(rs(root)),pushup(root);
int y=find_node(k);
splay(y);
int z=get_min(rs(root));
splay(z,root);
ls(rs(root))=x,fa(x)=rs(root);
pushup(rs(root)),pushup(root);
}
bool flag;
void dfs(int x,int n)
{
pushdown(x);
if(~ls(x))dfs(ls(x),n);
if(x!=0 && x!=n+1)
{
if(flag)printf(" ");
printf("%d",x);
flag=true;
}
if(~rs(x))dfs(rs(x),n);
}
void init(void)
{
flag=false;
root=idx=-1;
memset(tree,-1,sizeof(tree));
}
int main()
{
int n,q;
while(~scanf("%d%d",&n,&q) && ~n)
{
init();
for(int i=0; i<=n+1; i++)
insrt(i);
char op[5];
int x,y,z;
while(q--)
{
scanf("%s%d%d",op,&x,&y);
if(op[0]=='C')
{
scanf("%d",&z);
cut(x,y,z);
}
if(op[0]=='F')flip(x,y);
}
dfs(root,n);
printf("\n");
}
return 0;
}
区间删除:
#define ls(x) tree[x].lson
#define rs(x) tree[x].rson
#define fa(x) tree[x].pre
#define grafa(x) tree[tree[x].pre].pre
struct node
{
int pre,lson,rson;
int val,cont,siz;
node(int pre=-1,int lson=-1,int rson=-1,
int val=0,int cont=0,int siz=0):
pre(pre),lson(lson),rson(rson),
val(val),cont(cont),siz(siz) {}
} tree[200005];
int root=-1,idx=-1;
void pushup(int x)
{
tree[x].siz=tree[x].cont;
if(!x)tree[x].siz=0;
if(~ls(x))
tree[x].siz+=tree[ls(x)].siz;
if(~rs(x))
tree[x].siz+=tree[rs(x)].siz;
}
void zig(int x)
{
int y=fa(x);
if(~fa(y))
if(ls(fa(y))==y)
ls(fa(y))=x;
else rs(fa(y))=x;
fa(x)=fa(y),fa(y)=x;
ls(y)=rs(x);
if(~ls(y))fa(ls(y))=y;
rs(x)=y;
if(fa(x)==-1)root=x;
pushup(y),pushup(x);
}
void zag(int x)
{
int y=fa(x);
if(~fa(y))
if(ls(fa(y))==y)
ls(fa(y))=x;
else rs(fa(y))=x;
fa(x)=fa(y),fa(y)=x;
rs(y)=ls(x);
if(~rs(y))fa(rs(y))=y;
ls(x)=y;
if(fa(x)==-1)root=x;
pushup(y),pushup(x);
}
void splay(int x,int wz=-1)
{
while(x!=wz && fa(x)!=wz)
{
if(grafa(x)==wz)
if(ls(fa(x))==x)zig(x);
else zag(x);
else if(ls(fa(x))==x && ls(grafa(x))==fa(x))
zig(fa(x)),zig(x);
else if(rs(fa(x))==x && rs(grafa(x))==fa(x))
zag(fa(x)),zag(x);
else if(ls(fa(x))==x && rs(grafa(x))==fa(x))
zig(x),zag(x);
else if(rs(fa(x))==x && ls(grafa(x))==fa(x))
zag(x),zig(x);
}
}
int get_min(int x)
{
while(~ls(x))x=ls(x);
return x;
}
int get_max(int x)
{
while(~rs(x))x=rs(x);
return x;
}
int find_node(int val)
{
int x=root;
while(~x)
{
if(tree[x].val==val)
{
splay(x);
return x;
}
if(val<tree[x].val)
x=ls(x);
else x=rs(x);
}
return -1;
}
void insrt(int val)
{
int x=root,y=find_node(val);
if(~y)
{
tree[y].cont++;
tree[y].siz++;
return;
}
while(~x)
{
y=x;
if(val<tree[x].val)
x=ls(x);
else x=rs(x);
}
x=++idx;
tree[x]=node(y,-1,-1,val,1,1);
if(!x)tree[x].siz=0;
if(y==-1)root=x;
else
{
if(val<tree[y].val)
ls(y)=x;
else rs(y)=x;
pushup(y),splay(x);
}
}
int small_equel(int val)
{
int x=root,y=-1;
while(~x)
{
if(tree[x].val<=val && (y==-1 ||
(~y && tree[x].val>tree[y].val)))
y=x;
if(val<=tree[x].val)x=ls(x);
else x=rs(x);
}
splay(y);
return tree[y].val;
}
int smaller(int val,int wz=-1)
{
int x=root,y=-1;
while(~x)
{
if(tree[x].val<val && (y==-1 ||
(~y && tree[x].val>tree[y].val)))
y=x;
if(val<=tree[x].val)x=ls(x);
else x=rs(x);
}
splay(y,wz);
return y;
}
int bigger(int val,int wz=-1)
{
int x=root,y=-1;
while(~x)
{
if(tree[x].val>val && (y==-1 ||
(~y && tree[x].val<tree[y].val)))
y=x;
if(val<tree[x].val)x=ls(x);
else x=rs(x);
}
splay(y,wz);
return y;
}
void delet(int l,int r)
{
bigger(r,smaller(l));
ls(rs(root))=-1;
pushup(rs(root));
pushup(root);
}
int main()
{
insrt(-1),insrt(1e9+7);
int T;
scanf("%d",&T);
while(T--)
{
char op[2];
scanf("%s",op);
if(op[0]=='I')
{
int x;
scanf("%d",&x);
insrt(x);
}
if(op[0]=='Q')
{
int x;
scanf("%d",&x);
printf("%d\n",small_equel(x));
}
if(op[0]=='D')
{
int l,r;
scanf("%d%d",&l,&r);
delet(l,r);
}
}
return 0;
}
区间加/删除 询问区间和:
#define ls(x) tree[x].lson
#define rs(x) tree[x].rson
#define fa(x) tree[x].pre
#define grafa(x) tree[tree[x].pre].pre
struct node
{
int pre,lson,rson,id,siz;
ll val,sum,lazy;
node(int a=-1,int b=-1,int c=-1,int d=0,
int e=0,ll f=0,ll g=0,ll h=0):
pre(a),lson(b),rson(c),id(d),
siz(e),val(f),sum(g),lazy(h) {}
} tree[200005];
int root=-1,idx=-1;
void pushup(int x)
{
tree[x].sum=tree[x].val;
tree[x].siz=(x!=0);
if(~ls(x))
{
tree[x].sum+=tree[ls(x)].sum;
tree[x].siz+=tree[ls(x)].siz;
}
if(~rs(x))
{
tree[x].sum+=tree[rs(x)].sum;
tree[x].siz+=tree[rs(x)].siz;
}
}
void zig(int x)
{
int y=fa(x);
if(~fa(y))
if(ls(fa(y))==y)
ls(fa(y))=x;
else rs(fa(y))=x;
fa(x)=fa(y),fa(y)=x;
ls(y)=rs(x);
if(~ls(y))fa(ls(y))=y;
rs(x)=y;
if(fa(x)==-1)root=x;
pushup(y),pushup(x);
}
void zag(int x)
{
int y=fa(x);
if(~fa(y))
if(ls(fa(y))==y)
ls(fa(y))=x;
else rs(fa(y))=x;
fa(x)=fa(y),fa(y)=x;
rs(y)=ls(x);
if(~rs(y))fa(rs(y))=y;
ls(x)=y;
if(fa(x)==-1)root=x;
pushup(y),pushup(x);
}
void splay(int x,int wz=-1)
{
while(x!=wz && fa(x)!=wz)
if(grafa(x)==wz)
if(ls(fa(x))==x)zig(x);
else zag(x);
else if(ls(fa(x))==x && ls(grafa(x))==fa(x))
zig(fa(x)),zig(x);
else if(rs(fa(x))==x && rs(grafa(x))==fa(x))
zag(fa(x)),zag(x);
else if(ls(fa(x))==x && rs(grafa(x))==fa(x))
zig(x),zag(x);
else if(rs(fa(x))==x && ls(grafa(x))==fa(x))
zag(x),zig(x);
}
inline void pushdown(int id)
{
if(!tree[id].lazy)return;
ll add=tree[id].lazy;
if(~ls(id))
{
tree[ls(id)].val+=add;
tree[ls(id)].lazy+=add;
tree[ls(id)].sum+=tree[ls(id)].siz*add;
}
if(~rs(id))
{
tree[rs(id)].val+=add;
tree[rs(id)].lazy+=add;
tree[rs(id)].sum+=tree[rs(id)].siz*add;
}
tree[id].lazy=0;
pushup(id);
}
void insrt(int id,ll val)
{
int x=root,y=-1;
while(~x)
{
pushdown(y=x);
if(id<tree[x].id)
x=ls(x);
else x=rs(x);
}
x=++idx;
tree[x]=node(y,-1,-1,id,1,val,val);
if(y==-1)root=x;
else
{
if(id<tree[y].id)
ls(y)=x;
else rs(y)=x;
pushup(y),splay(x);
}
}
int smaller(int id,int wz=-1)
{
int x=root,y=-1;
while(~x)
{
pushdown(x);
if(tree[x].id<=id && (y==-1 ||
(~y && tree[x].id>tree[y].id)))
y=x;
if(id<=tree[x].id)x=ls(x);
else x=rs(x);
}
splay(y,wz);
return y;
}
int bigger(int id,int wz=-1)
{
int x=root,y=-1;
while(~x)
{
pushdown(x);
if(tree[x].id>=id && (y==-1 ||
(~y && tree[x].id<tree[y].id)))
y=x;
if(id<tree[x].id)x=ls(x);
else x=rs(x);
}
splay(y,wz);
return y;
}
ll get_sum(int l,int r)
{
bigger(r+1,smaller(l-1));
return tree[ls(rs(root))].sum;
}
void add(int l,int r,ll val)
{
bigger(r+1,smaller(l-1));
int x=ls(rs(root));
tree[x].val+=val;
tree[x].lazy+=val;
tree[x].sum+=tree[x].siz*val;
pushdown(rs(root));
pushup(root);
}
void delet(int l,int r)
{
bigger(r+1,smaller(l-1));
ls(rs(root))=-1;
pushup(rs(root));
pushup(root);
}
int main()
{
int q;
insrt(0,0),insrt(100000005,0);
scanf("%d",&q);
while(q--)
{
char op[2];
int x,y;
scanf("%s%d%d",op,&x,&y);
x=min(max(1,x),100000000);
y=min(max(1,y),100000000);
if(op[0]=='I')insrt(x,(ll)y);
if(op[0]=='Q')printf("%lld\n",get_sum(x,y));
if(op[0]=='D')delet(x,y);
if(op[0]=='M')
{
ll z;
scanf("%lld",&z);
add(x,y,z);
}
}
return 0;
}
网友评论