Code:
```cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 200010;
int n, m, q, a[N * 3], a_[N], oo[N], xx[N], yy[N], kk[N], ss[N];
namespace fentree {
int val[N * 3];
void modify (int p, int v) {
if (p == 0) {
return ;
}
for (; p <= n; p += p & (-p)) {
val[p] += v;
}
}
int query (int p) {
if (p == 0) {
return 0;
}
int s = 0;
for (; p >= 1; p -= p & (-p)) {
s += val[p];
}
return s;
}
}
int qry[N * 3], qry1[N * 3], qry2[N * 3], cnt;
void binary (int l, int r, int ql, int qr) {
if (l > r || ql > qr) {
return ;
}
cnt++;
if (l == r) {
for (int i = ql; i <= qr; i++) {
ss[qry[i]] = l;
}
return ;
}
int mid = (l + r) >> 1;
qry1[0] = qry2[0] = 0;
for (int i = ql; i <= qr; i++) {
if (oo[qry[i]] == 1) {
int t = fentree::query (yy[qry[i]]) - fentree::query (xx[qry[i]] - 1);
if (t >= kk[qry[i]]) {
qry1[++qry1[0]] = qry[i];
} else {
kk[qry[i]] -= t;
qry2[++qry2[0]] = qry[i];
}
} else {
if (yy[qry[i]] <= mid) {
fentree::modify (xx[qry[i]], kk[qry[i]]);
qry1[++qry1[0]] = qry[i];
} else {
qry2[++qry2[0]] = qry[i];
}
}
}
for (int i = 1; i <= qry1[0]; i++) {
if (oo[qry1[i]] == 2) {
fentree::modify (xx[qry1[i]], -kk[qry1[i]]);
}
}
int tmp = qry1[0];
for (int i = 1; i <= qry1[0]; i++) {
qry[i + ql - 1] = qry1[i];
}
for (int i = 1; i <= qry2[0]; i++) {
qry[i + ql + tmp - 1] = qry2[i];
}
binary (l, mid, ql, ql + tmp - 1);
binary (mid + 1, r, ql + tmp, qr);
}
int main () {
scanf ("%d%d", &n, &q);
for (int i = 1; i <= n; i++) {
scanf ("%d", &a[i]);
a_[i] = a[i];
oo[i] = 2;
qry[i] = xx[i] = i;
yy[i] = a[i];
kk[i] = 1;
}
int q_ = n;
for (int i = 1; i <= q; i++) {
char op[5];
q_++;
qry[q_] = q_;
scanf ("%s%d%d", op, &xx[q_], &yy[q_]);
if (op[0] == 'Q') {
oo[q_] = 1;
scanf ("%d", &kk[q_]);
} else {
q_++;
qry[q_] = q_;
oo[q_] = 2;
xx[q_] = xx[q_ - 1];
yy[q_] = yy[q_ - 1];
a[++n] = yy[q_];
kk[q_] = 1;
oo[q_ - 1] = 2;
yy[q_ - 1] = a_[xx[q_]];
kk[q_ - 1] = -1;
a_[xx[q_]] = yy[q_];
}
}
sort (a + 1, a + n + 1);
m = unique (a + 1, a + n + 1) - a - 1;
for (int i = 1; i <= q_; i++) {
if (oo[i] == 1) {
continue;
}
int l = 1, r = m, s = 0;
while (l <= r) {
int mid = (l + r) >> 1;
if (a[mid] <= yy[i]) {
s = mid;
l = mid + 1;
} else {
r = mid - 1;
}
}
yy[i] = s;
}
binary (1, m, 1, q_);
for (int i = 1; i <= q_; i++) {
if (oo[i] == 1) {
printf ("%d\n", a[ss[i]]);
}
}
return 0;
}
```
Status: [link](https://www.luogu.com.cn/record/116960354)
by denominator @ 2023-07-22 19:36:08
不仅是本地，所有能交的地方都可 AC
[link1](https://hydro.ac/d/bzoj/record/64bbbfb2b65f702f3c331f61)
[link2](https://vjudge.net/solution/44343718)（开不了黑暗爆炸 oj 就在 vj 上交了）
by denominator @ 2023-07-22 19:46:18
并且我们可以看到，\#1~\#10 的行尾为 CRLF，而 \#11~\#20 的行尾为 LF。
[证据](https://www.luogu.com.cn/record/116964670)，它 `getchar` 得到一个 `\r` 就会 `assert` 掉，否则会一直 `getchar` 直至 TLE（~~因为我不知道怎么判断 EOF~~）
by denominator @ 2023-07-22 19:54:42
不用了，发现问题了：`oo`、`xx`、`yy`、`kk`、`ss` 数组开小了！
by denominator @ 2023-07-22 20:31:31