前置知识

动态开点权值线段树

相信各位都会

线段树合并

我们考虑对于两棵权值线段树，由于动态开点的缘故，这两棵树都是不满的

我们考虑能不能把这两棵树所保存的信息合并在一起

我们考虑这么一件事就是说，由于树不满，我们可以暴力扫

分为三种情况(设把 \(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\)

例题\(\color{yellow}线段树分裂\)

代码

#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";
		}
	}
}