\(\text{Problem}\)
动态区间第 \(k\) 小
Dynamic Rankings
\(\text{Analysis}\)
整体二分
原本一个询问可二分,但多个询问效率太低
考虑离线,把修改和询问扔到一起
二分答案,运用树状数组之类的东西处理完修改操作
依次检查询问,划分左右,初步确定每个询问的答案值域,修改操作相应地划分到有必要的一边(左右)
\(\text{Code}\)
#include<cstdio>
using namespace std;
const int N = 1e5 + 5;
int n, m, cnt, a[N], ans[N], T[N];
struct node{
int ty, l, r, k, id;
}q[N * 3], q1[N * 3], q2[N * 3];
inline void read(int &x)
{
x = 0; char ch = getchar();
while (ch < '0' || ch > '9') ch = getchar();
while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
}
inline int lowbit(int x){return x & (-x);}
inline void add(int x, int v){for(; x <= n; x += lowbit(x)) T[x] += v;}
inline int query(int x)
{
int ret = 0;
for(; x; x -= lowbit(x)) ret += T[x];
return ret;
}
void solve(int l, int r, int ql, int qr)
{
if (ql > qr) return;
if (l == r)
{
for(int i = ql; i <= qr; i++) ans[q[i].id] = l;
return;
}
int ct1 = 0, ct2 = 0, mid = (l + r) >> 1;
for(int i = ql; i <= qr; i++)
{
if (q[i].ty == 1)
{
if (q[i].l <= mid) add(q[i].r, q[i].k), q1[++ct1] = q[i];
else q2[++ct2] = q[i];
}
else{
int sum = query(q[i].r) - query(q[i].l - 1);
if (sum >= q[i].k) q1[++ct1] = q[i];
else q[i].k -= sum, q2[++ct2] = q[i];
}
}
for(int i = 1; i <= ct1; i++)
if (q1[i].ty == 1) add(q1[i].r, -q1[i].k);
for(int i = 1; i <= ct1; i++) q[ql + i - 1] = q1[i];
for(int i = 1; i <= ct2; i++) q[ql + ct1 + i - 1] = q2[i];
solve(l, mid, ql, ql + ct1 - 1);
solve(mid + 1, r, ql + ct1, qr);
}
int main()
{
read(n), read(m);
for(int i = 1; i <= n; i++) read(a[i]), q[++cnt] = node{1, a[i], i, 1};
char op[3];
for(int i = 1, l, r, k; i <= m; i++)
{
scanf("%s", op), read(l), read(r);
if (op[0] == 'C') q[++cnt] = node{1, a[l], l, -1}, q[++cnt] = node{1, a[l] = r, l, 1};
else read(k), q[++cnt] = node{2, l, r, k, i};
}
solve(0, 1e9, 1, cnt);
for(int i = 1; i <= m; i++)
if (ans[i]) printf("%d\n", ans[i]);
}