1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
| #include<bits/stdc++.h>
using namespace std;
#define int long long
const int MAXn = 2e5;
const int MAXlayn = 19;
const int MAXm = 2e5;
template <typename T>
inline void read(T &a) {
char c;for (c = getchar(); (c < '0' || c > '9') && c != '-'; c = getchar());bool f = c == '-';T x = f ? 0 : (c ^ '0');for (c = getchar(); c >= '0' && c <= '9'; c = getchar()) {x = x * 10 + (c ^ '0');}a = f ? -x : x;
}
template <typename T, typename ...Argv>
inline void read(T &a, Argv &...argv) {
read(a), read(argv...);
}
const int MAXnd = MAXn * 4 + MAXm * MAXlayn * 2;
int cntroot, root[MAXm + 10];
int cntnd, ls[MAXnd + 10], rs[MAXnd + 10];
int sum[MAXnd + 10];
inline void pushup(int id) {
sum[id] = sum[ls[id]] + sum[rs[id]];
}
int build(int *a, int le, int ri) {
int id = ++cntnd;
if (le == ri) {
sum[id] = a[le];
} else {
int mid = (le + ri) >> 1;
ls[id] = build(a, le, mid);
rs[id] = build(a, mid + 1, ri);
pushup(id);
}
return id;
}
void modify(int &id, int p, int v, int le, int ri) {
if (id == 0) id = ++cntnd;
if (le == ri) {
sum[id] += v;
} else {
int mid = (le + ri) >> 1;
if (p <= mid) modify(ls[id], p, v, le, mid);
else modify(rs[id], p, v, mid + 1, ri);
pushup(id);
}
}
int query1(int id, int l, int r, int le, int ri) {
if (id == 0) return 0;
if (le >= l && ri <= r) {
return sum[id];
} else {
int mid = (le + ri) >> 1, ans = 0;
if (l <= mid) ans += query1(ls[id], l, r, le, mid);
if (r > mid) ans += query1(rs[id], l, r, mid + 1, ri);
return ans;
}
}
int query2(int id, int rk, int le, int ri) {
if (le == ri) {
return le;
} else {
int mid = (le + ri) >> 1;
if (rk <= sum[ls[id]]) {
return query2(ls[id], rk, le, mid);
} else {
return query2(rs[id], rk - sum[ls[id]], mid + 1, ri);
}
}
}
int merge(int id1, int id2, int le, int ri) {
if (id1 == 0 || id2 == 0) return id1 + id2;
if (le == ri) {
sum[id1] += sum[id2];
} else {
int mid = (le + ri) >> 1;
ls[id1] = merge(ls[id1], ls[id2], le, mid);
rs[id1] = merge(rs[id1], rs[id2], mid + 1, ri);
pushup(id1);
}
return id1;
}
int split(int id, int p, int le, int ri) {
if (id == 0) return 0;
int nwid = ++cntnd;
if (le == ri) {
;
} else {
int mid = (le + ri) >> 1;
if (p <= mid) {
rs[nwid] = rs[id];
rs[id] = 0;
ls[nwid] = split(ls[id], p, le, mid);
} else {
rs[nwid] = split(rs[id], p, mid + 1, ri);
}
pushup(id); pushup(nwid);
}
return nwid;
}
int n, m;
int a[MAXn + 10];
int Query2(int rootid, int rk) {
if (rk > sum[rootid]) return -1;
return query2(rootid, rk, 1, n);
}
int Split(int &rootid, int l, int r) {
int lid, mdid, rid;
rid = split(rootid, r, 1, n);
if (l == 1) {
mdid = rootid;
lid = 0;
} else {
mdid = split(rootid, l - 1, 1, n);
lid = rootid;
}
rootid = merge(lid, rid, 1, n);
return mdid;
}
signed main() {
read(n, m);
for (int i = 1; i <= n; ++i) {
read(a[i]);
}
root[++cntroot] = build(a, 1, n);
for (int i = 1, opt, ver, x, y; i <= m; ++i) {
read(opt, ver);
if (opt == 0) {
read(x, y);
root[++cntroot] = Split(root[ver], x, y);
} else if (opt == 1) {
read(x);
root[ver] = merge(root[ver], root[x], 1, n);
} else if (opt == 2) {
read(x, y);
modify(root[ver], y, x, 1, n);
} else if (opt == 3) {
read(x, y);
printf("%lld\n", query1(root[ver], x, y, 1, n));
} else {
read(x);
printf("%lld\n", Query2(root[ver], x));
}
}
return 0;
}
|
