提交记录

#include<bits/stdc++.h>
#define int long long
using namespace std;
char In[1 << 20], *ss = In, *tt = In;
#define getchar() (ss == tt && (tt = (ss = In) + fread(In, 1, 1 << 20, stdin), ss == tt) ? EOF : *ss++)
inline signed int read() {
	signed int x = 0, f = 1;
	char ch = getchar();
	while (!isdigit(ch)) {
		if (ch == '-')f = -1;
		ch = getchar();
	}
	while (isdigit(ch)) {
		x = x * 10 + ch - '0';
		ch = getchar();
	}
	return x * f;
}
const int maxn = 2e5 + 100;
struct node {
	int sum, l, r;
} t[maxn << 5];
int n, m, rt[maxn], tot, num;
stack<int> stk;
inline void del(int &p) {
	stk.push(p);
	t[p].sum = t[p].l = t[p].r = 0;
	return;
}
inline int create() {
	if (!stk.empty()) {
		int l = stk.top();
		stk.pop();
		return l;
	}
	return ++tot;
}
int query(int p, int l, int r, int k) {
	if (p == 0 || k <= 0) return -1;
	if (l == r) {
		if (t[p].sum >= k) return l;
		return -1;
	}
	int lc = t[p].l, rc = t[p].r;
	int mid = l + r >> 1;
	if (lc && t[lc].sum >= k)return query(lc, l, mid, k);
	else return query(rc, mid + 1, r, k - t[lc].sum);
}
int query(int p, int l, int r, int L, int R) {
	if (p == 0)return 0;
	if (r < L && R < l)return 0;
	if (L <= l && r <= R)return t[p].sum;
	int mid = l + r >> 1;
	int lc = t[p].l, rc = t[p].r;
	return query(lc, l, mid, L, R) + query(rc, mid + 1, r, L, R);
}
inline void pushup(int p) {
	int lc = t[p].l, rc = t[p].r;
	t[p].sum = t[lc].sum + t[rc].sum;
	return;
}
int merge(int a, int b, int l, int r) {
	if (a == 0)return b;
	if (b == 0)return a;
	if (l == r) {
		t[a].sum += t[b].sum;
		del(b);
		return a;
	}
	int mid = l + r >> 1;
	t[a].l = merge(t[a].l, t[b].l, l, mid);
	t[a].r = merge(t[a].r, t[b].r, mid + 1, r);
	pushup(a);
	del(b);
	return a;
}
void split(int a, int &b, int k) {
	if (!a)return ;
	b = create();
	int lc = t[a].l, rc = t[a].r;
	int cnt = t[lc].sum;
	if (cnt < k)split(t[a].r, t[b].r, k - cnt);
	else swap(t[a].r, t[b].r);
	if (cnt > k)split(t[a].l, t[b].l, k);
	t[b].sum = t[a].sum - k, t[a].sum = k;
	return;
}
inline void cut(int p, int x, int y) {
	int t1 = query(rt[p], 1, n, 1, y);
	int t2 = query(rt[p], 1, n, x, y);
	split(rt[p], rt[++num], t1 - t2);
	int tmp = 0;
	split(rt[num], tmp, t2);
	rt[p] = merge(rt[p], tmp, 1, n);
	return;
}
void modify(int &p, int l, int r, int x, int v) {
	if (p == 0)p = create();
	if (l == r) {
		t[p].sum += v;
		return;
	}
	int mid = l + r >> 1;
	if (x <= mid)
		modify(t[p].l, l, mid, x, v);
	else
		modify(t[p].r, mid + 1, r, x, v);
	pushup(p);
	return;
}
signed main() {
	n = read(), m = read();
	rt[num = 1] = ++tot;
	for (int i = 1; i <= n; ++i) {
		int x = read();
		modify(rt[1], 1, n, i, x);
	}
	while (m--) {
		int op = read();
		if (op == 0) {
			int p = read(), x = read(), y = read();
			cut(p, x, y);
		} else if (op == 1) {
			int p = read(), t = read();
			rt[p] = merge(rt[p], rt[t], 1, n);
		} else if (op == 2) {
			int p = read(), x = read(), q = read();
			modify(rt[p], 1, n, q, x);
		} else if (op == 3) {
			int p = read(), x = read(), y = read();
			printf("%lld\n", query(rt[p], 1, n, x, y));
		} else {
			int p = read(), k = read();
			printf("%lld\n", query(rt[p], 1, n, k));
		}
	}
}