P5494.【模闆】線段樹分裂

【模闆】線段樹分裂

給出一個可重集a（編号為1），它支援以下操作：

0 p x y

：将可重集p中大于等于x且小于等于y的值放入一個新的可重集中（新可重集編号為從2開始的正整數，是上一次産生的新可重集的編号+1）

1 p t

：将可重集t中的數放入可重集p中，且清空可重集t（資料保證在此後的操作中不會出現可重集t）

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+100;
const int M=maxn*40;
int n,m;
int lson[M];
int rson[M];
long long sum[M];
int T[maxn];
int cnt=0;
int tot;
//删掉的節點個數 
//空間回收，可以回收線段樹合并後沒有用的節點
int rb[maxn];//垃圾桶
void del (int &u) {
	lson[u]=rson[u]=sum[u]=0;
	rb[++tot]=u;
	u=0;
} 
int New() {
	//申請空間
	if (tot) return rb[tot--];
	return ++cnt; 
}

int a[maxn];//原始數組
void pushup (int u) {
	sum[u]=sum[lson[u]]+sum[rson[u]];
} 
void build (int &u,int l,int r) {
	if (!u) u=New();
	if (l==r) {
		sum[u]=a[l];
		return;
	}
	int mid=(l+r)>>1;
	build(lson[u],l,mid);
	build(rson[u],mid+1,r);
	pushup(u);
}
void merge (int &rt1,int &rt2,int l,int r) {
	if (!rt1||!rt2) {
		rt1+=rt2;
		return;
	}
	if (l==r) {
		sum[rt1]+=sum[rt2];
		del(rt2);
		return;
	}
	int mid=(l+r)>>1;
	merge(lson[rt1],lson[rt2],l,mid);
	merge(rson[rt1],rson[rt2],mid+1,r);
	del(rt2);
	pushup(rt1);
} 
void split (int &rt1,int &rt2,int l,int r,int L,int R) {
	if (R<l||r<L) return;
	if (!rt1) return;
	if (L<=l&&r<=R) {
		rt2=rt1;
		rt1=0;
		return;
	}
	if (!rt2) rt2=New();
	int mid=(l+r)>>1;
	split(lson[rt1],lson[rt2],l,mid,L,R);
	split(rson[rt1],rson[rt2],mid+1,r,L,R);
	pushup(rt1);
	pushup(rt2);
}
void up (int &rt,int l,int r,int p,int v) {
	if (p<l||p>r) return;
	if (!rt) rt=New();
	if (l==r) {
		sum[rt]+=v;
		return; 
	}
	int mid=(l+r)>>1;
	up(lson[rt],l,mid,p,v);
	up(rson[rt],mid+1,r,p,v);
	pushup(rt);
}
long long query_sum (int rt,int l,int r,int L,int R) {
	if (R<l||r<L) return 0;
	if (!rt) return 0;
	if (L<=l&&r<=R) return sum[rt];
	int mid=(l+r)>>1;
	return query_sum(lson[rt],l,mid,L,R)+query_sum(rson[rt],mid+1,r,L,R);
}
int query_kth (int rt,int l,int r,long long k) {
	if (k<=0) return -1;
	if (l==r) return l;
	int mid=(l+r)>>1;
	if (sum[lson[rt]]>=k) return query_kth(lson[rt],l,mid,k);
	return query_kth(rson[rt],mid+1,r,k-sum[lson[rt]]);
}
int ttt=1;
int main () {
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;i++) scanf("%d",a+i);
	build(T[1],1,n);
	while (m--) {
		int op;
		scanf("%d",&op);
		if (op==0) {
			int p,x,y;
			scanf("%d%d%d",&p,&x,&y);
			split(T[p],T[++ttt],1,n,x,y);
			//分裂出一顆新樹 
		}
		else if (op==1) {
			int p,t;
			scanf("%d%d",&p,&t);
			merge(T[p],T[t],1,n);
		}
		else if (op==2) {
			int p,x,y;
			scanf("%d%d%d",&p,&x,&y);
			up(T[p],1,n,y,x);
		}
		else if (op==3) {
			int p,x,y;
			scanf("%d%d%d",&p,&x,&y);
			printf("%lld\n",query_sum(T[p],1,n,x,y));
		}
		else if (op==4) {
			int x,y;
			int ans=0;
			scanf("%d%d",&x,&y);
			if (query_sum(T[x],1,n,1,n)<y) ans=-1;
			else ans=query_kth(T[x],1,n,y);
			printf("%d\n",ans);
		}
	}
}