前置知识
动态开点权值线段树
相信各位都会
线段树合并
我们考虑对于两棵权值线段树，由于动态开点的缘故，这两棵树都是不满的
我们考虑能不能把这两棵树所保存的信息合并在一起
我们考虑这么一件事就是说，由于树不满，我们可以暴力扫
分为三种情况(设把 \(b\) 所在树并到 \(a\) 内，\(a\) 和 \(b\) 为两棵树中位置对应的节点)
-
若扫到节点 \(now\) 时 \(a\) 或 \(b\) 为 \(0\) 也就是说是空节点，则返回 \(a+b\) (也就是非空那个，或者两个都空)
-
否则把 \(val_a\to val_a+val_b\) 然后递归左右儿子，回溯回来后删除 \(b\)
然后 \(\dots\) 没了
是的就是这么敷衍
int merge(int a,int b){//线段树合并
if(!a or !b) return a+b;
val[a]+=val[b];
son[a][0]=merge(son[a][0],son[b][0]);
son[a][1]=merge(son[a][1],son[b][1]);
del(b);
return a;
}
线段树分裂
什么fhq
于是我们真的类比 fhq
考虑把前 \(k\) 个和后面的分裂成两棵树
等会，前 \(k\) 个啥啊
前 \(k\) 个叶子节点，是的分裂标准是叶子节点
我们考虑如何分裂
如果左儿子权值大于等于 \(k\) 那么直接把整个右子树都送给裂出去的树
如果左儿子权值小于那么递归右子树，\(k\) 减去左子树权值
如果左子树大递归左子树 \(k\) 不变
void split(int x,int &y,T k){//分裂
if(!x) return;
y=nnd();
T v=val[son[x][0]];
if(k>v){
split(son[x][1],son[y][1],k-v);
}
else swap(son[x][1],son[y][1]);
if(k<v){
split(son[x][0],son[y][0],k);
}
val[y]=val[x]-k;
val[x]=k;
}
按照我们的设想左子树权值为 \(k\)
代码
#include<bits/stdc++.h>
using namespace std;
const int N=4e5+5;
typedef long long ll;
template<typename T>
struct QZ_seg_tr{//权值线段树(带分裂合并)
int rt[N];
T val[N*20];
int tot=1,cnt;
int son[N*20][2];
int pol[N*20],dcnt;//这是一个特别的优化，开一个内存池把删掉的点的编号存下来循环利用
#define ls (son[now][0])
#define rs (son[now][1])
//适当宏增加可读性
int nnd(){
return dcnt?pol[dcnt--]:++cnt;
}
void del(int now){
pol[++dcnt]=now;
ls=rs=val[now]=0;
}
//新建和删除节点
void modi(int &now,int l,int r,int p,int v){//单点修改
if(!now){
now=nnd();
}
val[now]+=v;
if(l==r) return;
int mid=(l+r)>>1;
if(p<=mid) modi(ls,l,mid,p,v);
else modi(rs,mid+1,r,p,v);
}
T query(int now,int l,int r,int L,int R){
if(R<l or r<L) return 0;
if(L<=l and R>=r){
return val[now];
}
int mid=(l+r)>>1;
return query(ls,l,mid,L,R)+query(rs,mid+1,r,L,R);
}
int qk(int now,int l,int r,int v){//查询区间比它小的数的个数
if(l==r) return l;
int mid=(l+r)>>1;
if(val[ls]>=v) return qk(ls,l,mid,v);
else return qk(rs,mid+1,r,v-val[ls]);
}
int merge(int a,int b){//线段树合并
if(!a or !b) return a+b;
val[a]+=val[b];
son[a][0]=merge(son[a][0],son[b][0]);
son[a][1]=merge(son[a][1],son[b][1]);
del(b);
return a;
}
void split(int x,int &y,T k){//分裂
if(!x) return;
y=nnd();
T v=val[son[x][0]];
if(k>v){
split(son[x][1],son[y][1],k-v);
}
else swap(son[x][1],son[y][1]);
if(k<v){
split(son[x][0],son[y][0],k);
}
val[y]=val[x]-k;
val[x]=k;
}
};
QZ_seg_tr<long long> t;
int n,m;
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
int x;
cin>>x;
t.modi(t.rt[1],1,n,i,x);
}
while(m--){
int opt;cin>>opt;
int x,y,z;
if(!opt){
cin>>x>>y>>z;
ll q1=t.query(t.rt[x],1,n,1,z);
ll q2=t.query(t.rt[x],1,n,y,z);
int A=0;
t.split(t.rt[x],t.rt[++t.tot],q1-q2);
t.split(t.rt[t.tot],A,q2);
t.rt[x]=t.merge(t.rt[x],A);
}
else if(opt==1){
cin>>x>>y;
t.rt[x]=t.merge(t.rt[x],t.rt[y]);
}
else if(opt==2){
cin>>x>>y>>z;
t.modi(t.rt[x],1,n,z,y);
}
else if(opt==3){
cin>>x>>y>>z;
cout<<t.query(t.rt[x],1,n,y,z)<<"\n";
}
else{
cin>>x>>y;
if(t.val[t.rt[x]]<y) cout<<-1;
else
cout<<t.qk(t.rt[x],1,n,y);
cout<<"\n";
}
}
}