洛谷P5494 【模板】线段树分裂

传送门

  需要的前置知识：线段树合并。

  感觉会了线段树合并这个就很简单，线段树分裂就是在把一颗权值线段树值域在[x, y]的区间分裂出来单独成一个线段树，那么我们只需要从新树q和旧树p的根节点一起走，如果走到当前p被[x, y]完全包含的路径就把p的编号给q，并且把p改为0就行了，注意这里p和q要传引用，并且不能直接拿q = p这样p和q的地址会一样，所以一改开一个int类型tmp = p，q = tmp，p = 0然后我们return即可，然后注意这题卡空间需要废点优化，我们把线段树合并不需要的那一部分点存进stk数组，并且将这个结点的tr清空即可。

#include <iostream>
#include <algorithm>
#include <cstring>
#include <set>
#include <map>
#include <deque>
#include <vector>

typedef long long ll;
typedef std::pair<int, int> PII;
#define ls tr[u].l
#define rs tr[u].r

const int INF = 0x3f3f3f3f;
const int N = 2e5 + 10, M = 2e5 + 10;

int n, m;

int root[N], cnt, a[N];
int stk[N << 5], top;

struct node {
	int l, r;
	ll cnt;
}tr[N << 5];

inline int get() {
	if(!top) {
		return ++ cnt;
	} 

	int p = stk[top --];
	tr[p] = {0, 0, 0};
	
	return p;
}

inline void pushup(int u) {
	tr[u].cnt = tr[tr[u].l].cnt + tr[tr[u].r].cnt;
}

inline void build(int &u, int L, int R) {
	u = get();
	if(L == R) {
	
		tr[u].cnt = a[L];
		return ;
	} 
	
	int mid = L + R >> 1;
	build(tr[u].l, L, mid);
	build(tr[u].r, mid + 1, R);
	
	pushup(u);
}

inline void split(int &p, int &q, int L, int R, int x, int y) {
	if(!q) q = get();
	if(L >= x && R <= y) {
		q = p;
		p = 0;
		return ;
	}
	
	int mid = L + R >> 1;
	if(x <= mid)	split(tr[p].l, tr[q].l, L, mid, x, y);
	if(y > mid)	split(tr[p].r, tr[q].r, mid + 1, R, x, y);
	
	pushup(p);
	pushup(q);
}

inline int merge(int p, int q, int L, int R){
	if(!p)	return q;
	if(!q)	return p;
	stk[++ top] = q;
	if(L == R){
		tr[p].cnt += tr[q].cnt;
		return p;
	}	
	int mid = L + R >> 1;
	tr[p].l = merge(tr[p].l, tr[q].l, L, mid);
	tr[p].r = merge(tr[p].r, tr[q].r, mid + 1, R);

	pushup(p);
	return p;
}

inline void insert(int &p, int L, int R, ll x, int v) {
	if(!p) p = get();
	if(L == R) {
		tr[p].cnt += x;
		return ;
	}
	
	int mid = L + R >> 1;
	if(v <= mid)	insert(tr[p].l, L, mid, x, v);
	else insert(tr[p].r, mid + 1, R, x, v);
	
	pushup(p);
}

inline ll query(int p, int L, int R, int x, int y) {
	if(!p)	return 0;

	if(L >= x && R <= y)	return tr[p].cnt;
	
	int mid = L + R >> 1;
	ll res = 0;
	
	if(x <= mid)	res += query(tr[p].l, L, mid, x, y);
	if(y > mid) res += query(tr[p].r, mid + 1, R, x, y);
	
	return res;
}

inline int queryk(int p, int L, int R, ll k) {
	if(L == R)	return L;
	int mid = L + R >> 1;
	if(tr[tr[p].l].cnt < k) 	return queryk(tr[p].r, mid + 1, R, k - tr[tr[p].l].cnt);
	return queryk(tr[p].l, L, mid, k);
}

inline void solve() {
	std::cin >> n >> m;

	for (int i = 1; i <= n; i ++)	std::cin >> a[i];
	build(root[1], 1, n);
	
	int timestap = 1;
	for (int i = 1; i <= m; i ++) {
		int op;
		std::cin >> op;
		if (!op) {
			int p, x, y;
			std::cin >> p >> x >> y;
			split(root[p], root[++ timestap], 1, n, x, y);
	
		} else if (op == 1) {
			int p, q;
			std::cin >> p >> q;
			merge(root[p], root[q], 1, n);
			
			tr[root[i]].cnt << '\n';
		} else if (op == 2) {
			int p, v;
			ll x;
			std::cin >> p >> x >> v;
			insert(root[p], 1, n, x, v);

		} else if (op == 3) {
			int p, x, y;
			std::cin >> p >> x >> y;
			std::cout << query(root[p], 1, n, x, y) << '\n';
		} else {
			 int p;
			 ll k;
			 std::cin >> p >> k;
			 
			 if(tr[root[p]].cnt < k)	std::cout << "-1" << '\n';
			 else std::cout << queryk(root[p], 1, n, k) << '\n';
		}
	}
}

int main(void) {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    
   //freopen("D:\\in.txt","r",stdin); //输入重定向，输入数据将从D盘根目录下的in.txt文件中读取 
    int _ = 1;
    //std::cin >> _;
    while(_ --)
    	solve();

    return 0;
}