题目描述
给定一个含有 n 个数的序列 a1,a2…an，需要支持两种操作：
Q l r k表示查询下标在区间 [l,r] 中的第 k 小的数C x y表示将 (a_x) 改为 y
输入格式
第一行两个正整数 n,m，表示序列长度与操作个数。
第二行 n 个整数，表示 a1,a2…an。
接下来 m 行，每行表示一个操作，都为上述两种中的一个。
输出格式
对于每一次询问，输出一行一个整数表示答案。
输入输出样例
输入 #1
5 3
3 2 1 4 7
Q 1 4 3
C 2 6
Q 2 5 3
输出 #1
3
6
说明/提示
【数据范围】
对于 100% 的数据，(1le n,m le 10^5，1 le l le r le n，1 le k le r-l+1，1le x le n，0 le a_i,y le 10^9)。
#include <bits/stdc++.h>
using namespace std;
inline long long read() {
long long s = 0, f = 1; char ch;
while(!isdigit(ch = getchar())) (ch == '-') && (f = -f);
for(s = ch ^ 48;isdigit(ch = getchar()); s = (s << 1) + (s << 3) + (ch ^ 48));
return s * f;
}
const int N = 2e5 + 5, inf = 1e9;
int n, m, cnt, tot;
int a[N], t[N], ans[N];
struct que { int x, y, z, opt; } q[N << 2], ql[N << 2], qr[N << 2];
int lowbit(int x) { return x & (-x); }
void change(int x, int y) { for(; x <= N - 5; x += lowbit(x)) t[x] += y; }
int ask(int x) { int res = 0; for(; x ; x -= lowbit(x)) res += t[x]; return res; }
void work(int L, int R, int l, int r) {
if(l > r) return ;
if(L == R) {
for(int i = l;i <= r; i++) ans[q[i].opt] = L;
return ;
}
int mid = (L + R) >> 1;
int tmp1 = 0, tmp2 = 0;
for(int i = l;i <= r; i++) {
if(q[i].opt <= 0) {
if(q[i].y <= mid) change(q[i].x, q[i].z), ql[++tmp1] = q[i];
else qr[++tmp2] = q[i];
}
else {
int tmp = ask(q[i].y) - ask(q[i].x - 1);
if(tmp >= q[i].z) ql[++tmp1] = q[i];
else q[i].z -= tmp, qr[++tmp2] = q[i];
}
}
for(int i = l;i <= r; i++)
if(q[i].opt <= 0 && q[i].y <= mid) change(q[i].x, -q[i].z);
for(int i = 1;i <= tmp1; i++) q[l + i - 1] = ql[i];
for(int i = 1;i <= tmp2; i++) q[l + tmp1 + i - 1] = qr[i];
work(L, mid, l, l + tmp1 - 1); work(mid + 1, R, l + tmp1, r);
}
int main() {
n = read(); m = read();
for(int i = 1, x; i <= n; i ++) {
x = read(); a[i] = x;
q[++cnt].opt = 0; q[cnt].x = i; q[cnt].y = x; q[cnt].z = 1;
}
for(int i = 1, l, r, k;i <= m; i++) {
char ch; cin >> ch;
if(ch == 'Q') {
l = read(); r = read(); k = read();
q[++cnt].opt = ++tot; q[cnt].x = l; q[cnt].y = r; q[cnt].z = k;
}
if(ch == 'C') {
l = read(); r = read();
q[++cnt].opt = -1; q[cnt].x = l; q[cnt].y = a[l]; q[cnt].z = -1;
q[++cnt].opt = 0; q[cnt].x = l; q[cnt].y = r; q[cnt].z = 1;
a[l] = r;
}
}
work(-inf, inf, 1, cnt);
for(int i = 1;i <= tot; i++) printf("%d
", ans[i]);
return 0;
}