评测记录

#include <bits/stdc++.h>
using namespace std;

#define int ll

typedef long long ll;

const int MAX_N = 2e5 + 10;

struct NODE{
	ll val;
	int lson, rson;
};

NODE t[MAX_N << 5]; int cnt;
int rt[MAX_N], tot;
int sta[MAX_N], top;
int a[MAX_N];
int n, m;

int addnode(){ return top ? sta[top--] : ++cnt; }

void del(int id){ t[id].lson = t[id].rson = 0; sta[++top] = id; }

void pushup(int rt) { t[rt].val = t[t[rt].lson].val + t[t[rt].rson].val; }

void modify(int P, int l, int r, int val, int &rt){
	if (!rt) rt = addnode();
	//printf("P = %d, l = %d, r = %d, val = %d, rt = %d\n", P, l, r, val, rt);
	if (l == r){
		t[rt].val += val;
		return;
	}
	int mid = l + r >> 1;
	if (P <= mid) modify(P, l, mid, val, t[rt].lson);
		else modify(P, mid + 1, r, val, t[rt].rson);
	pushup(rt);
	return;
}

void split(int L, int R, int l, int r, int &rt1, int &rt2){
	if (l > R || r < L) return;
	if (!rt1) return;
	if (l >= L && r <= R){
		rt2 = rt1;
		rt1 = 0;
		return;
	}
	if (!rt2) rt2 = addnode();
	int mid = l + r >> 1;
	split(L, R, l, mid, t[rt1].lson, t[rt2].lson);
	split(L, R, mid + 1, r, t[rt1].rson, t[rt2].rson);
	pushup(rt1); pushup(rt2);
	return;
}

void merge(int l, int r, int &rt1, int &rt2){
	if (!rt1) return;
	if (!rt2){
		rt2 = rt1; return;
	} 
	if (l == r){
		t[rt2].val += t[rt1].val; del(rt1);
		return;
	} 
	int mid = l + r >> 1;
	merge(l, mid, t[rt1].lson, t[rt2].lson);
	merge(mid + 1, r, t[rt1].rson, t[rt2].rson);
	pushup(rt2); del(rt1);
	return;
}

ll query(int L, int R, int l, int r, int rt){
	if (rt == 0 || l > R || r < L) return 0;
	if (l >= L && r <= R) return t[rt].val;
	int mid = l + r >> 1;
	return query(L, R, l, mid, t[rt].lson) + query(L, R, mid + 1, r, t[rt].rson);
}

ll queryk(int l, int r, ll k, int rt){
	if (l == r) return l;
	int mid = l + r >> 1;
	if (t[t[rt].lson].val >= k) return queryk(l, mid, k, t[rt].lson);
		else return queryk(mid + 1, r, k - t[t[rt].lson].val, t[rt].rson);
}

signed main(){
	//freopen("mine.out", "w", stdout);
	scanf("%lld%lld", &n, &m); int u = max(n, m);
	rt[++tot] = cnt = 1;
	for (int i = 1; i <= n; i++){
		scanf("%lld", &a[i]);
		if (a[i] != 0) modify(i, 1, u, a[i], rt[1]);
	}
	while (m--){
		int opt, p, x, y, q; ll k;
		scanf("%lld", &opt);
		if (opt == 0){ //split
			scanf("%lld%lld%lld", &p, &x, &y);
			split(x, y, 1, u, rt[p], rt[++tot]);
		}else if (opt == 1){ // merge
			scanf("%lld%lld", &p, &x);
			rt[p]=merge(1, u, rt[x], rt[p]);
			rt[x]=0;
		}else if (opt == 2){ // modify
			scanf("%lld%lld%lld", &p, &x, &q);
			modify(q, 1, u, x, rt[p]);
		}else if (opt == 3){ // query x <= ? <= y
			scanf("%lld%lld%lld", &p, &x, &y);
			printf("%lld\n", query(x, y, 1, u, rt[p]));
		}else{ // query No.k
			scanf("%lld%lld", &p, &k);
			printf("%lld\n", k <= t[rt[p]].val ? queryk(1, u, k, rt[p]) : -1);
		}
	}
	return 0;
}