「Template」整体二分
带修的区间第 \(k\) 小。
#include
#include
#include
#include
using namespace std;
#define LL long long
#define rep(i, j, k) for(int i = (j); i <= (k); i ++)
#define per(i, j, k) for(int i = (j); i >= (k); i --)
const int Maxn = 1e5;
int n, m, tot;
char s[2];
int a[Maxn + 5], ans[Maxn + 5], Bit[Maxn + 5];
struct Node {
int l, r, k, id, opt;
} q[Maxn * 3 + 5];
queue < Node > q1, q2;
namespace BIT {
void Update (int x, int y) {
for (int i = x; i <= n; i += i & -i) Bit[i] += y;
}
int Sum (int x) {
int sum = 0;
for (int i = x; i; i -= i & -i) sum += Bit[i];
return sum;
}
}
using namespace BIT;
void Solve (int ql, int qr, int l, int r) { //当前处理的操作区间为 [ql,qr] ,值域区间为 [l,r]
if (ql > qr) return ;
if (l == r) { //找到答案
rep (i, ql, qr) {
if (q[i].opt == 0) ans[q[i].id] = l; //对于[ql,qr] 中的查询操作更新答案
}
return ;
}
int mid = (l + r) >> 1; //二分
rep (i, ql, qr) {
if (q[i].opt == 0) { //属于查询操作
int sum = Sum (q[i].r) - Sum (q[i].l - 1);
//进行了[ql,i-1]操作后,[q[i].l,q[i].r](查询的区间)中小于 mid 的数的个数
if (sum >= q[i].k) { //若个数大于询问的 k ,代表询问的答案小于 mid (答案更小才能让sum变小最终等于k),答案在[l,mid]
q1.push (q[i]); //放入[l,mid]的数组
} else { //否则,答案在[mid+1,r]
q[i].k -= sum; //减去[ql,i-1]操作中小于mid的数对答案排名产生的贡献
q2.push (q[i]); //放入[mid+1,r]的数组
}
} else { //属于 删除 / 插入
if (q[i].k <= mid) { //元素大小小于 mid
Update (q[i].id, q[i].opt); //根据 opt 添加/删除 其产生的贡献
q1.push (q[i]); //对于[l,mid]中的答案可能会产生贡献
}
else {
q2.push (q[i]); //对于[mid+1,r]中的答案可能会产生贡献
}
}
}
int pos = ql - 1;
while (q1.size ()) {
Node res = q1.front ();
if (res.opt) Update (res.id, -res.opt); //撤销
q[++ pos] = res; q1.pop ();
}
int now = pos; //以 now 为分界
while (q2.size ()) {
q[++ pos] = q2.front (); q2.pop ();
}
Solve (ql, now, l, mid);
Solve (now + 1, qr, mid + 1, r); //递归
}
int main () {
scanf ("%d %d", &n, &m);
rep (i, 1, n) {
scanf ("%d", &a[i]);
q[++ tot] = {0, 0, a[i], i, 1}; //将初始的数组看成插入元素
}
rep (i, 1, m) {
scanf ("%s", s + 1);
switch (s[1]) {
case 'Q' : {
int l, r, k;
scanf ("%d %d %d", &l, &r, &k);
q[++ tot] = {l, r, k, i, 0}; //查询操作
break;
}
case 'C' : {
int x, y;
scanf ("%d %d", &x, &y);
//将修改拆成 删除+插入
q[++ tot] = {0, 0, a[x], x, -1}; //删除
a[x] = y; //更新一下
q[++ tot] = {0, 0, a[x], x, 1}; //插入
break;
}
}
}
memset (ans, -1, sizeof ans);
Solve (1, tot, -1e9, 1e9);
rep (i, 1, m) {
if (~ans[i])
printf ("%d\n", ans[i]);
}
return 0;
}