动态排名
题目链接:ybt金牌导航6-6-2
题目大意
给你一个数组,然后会有两种操作:
修改一个位置的值和查询区间第 k 大。
思路
这题其实就跟不带修改的差不多。
(你修改你可以相当于一个删除再加入)
然后你就可以用整体二分做(数组数组维护排名)。
代码
#include<cstdio>
using namespace std;
struct node {
int id, x, y, k, op, tmp;
}q[150001], q1[150001], q2[150001];
int n, m, x, num, y, k, tot;
int ans[10001], a[50001], tmp[150001];
char op;
struct SZSJ {
int tr[150001];
void insert(int x, int y) {
for (; x <= n; x += x & (-x))
tr[x] += y;
}
int query(int x) {
int re = 0;
for (; x; x -= x & (-x))
re += tr[x];
return re;
}
}T;
void work(int l, int r, int L, int R) {
if (l > r) return ;
if (L == R) {
for (int i = l; i <= r; i++)
if (q[i].op == 1) ans[q[i].id] = L;
return ;
}
int mid = (1ll * L + R) >> 1;
for (int i = l; i <= r; i++) {
if (q[i].op == 0 && q[i].y <= mid) T.insert(q[i].x, 1);
if (q[i].op == 2 && q[i].y <= mid) T.insert(q[i].x, -1);
if (q[i].op == 1) {
tmp[i] = T.query(q[i].y) - T.query(q[i].x - 1);
}
}
int l1 = 0, l2 = 0;
for (int i = l; i <= r; i++) {
if (q[i].op == 1) {
if (tmp[i] + q[i].tmp >= q[i].k) q1[++l1] = q[i];
else q[i].tmp += tmp[i], q2[++l2] = q[i];
}
else if (q[i].y <= mid) q1[++l1] = q[i];
else q2[++l2] = q[i];
}
for (int i = l; i <= r; i++) {
if (q[i].op == 0 && q[i].y <= mid) T.insert(q[i].x, -1);
if (q[i].op == 2 && q[i].y <= mid) T.insert(q[i].x, 1);
}
for (int i = 1; i <= l1; i++) q[l + i - 1] = q1[i];
for (int i = 1; i <= l2; i++) q[l + l1 + i - 1] = q2[i];
work(l, l + l1 - 1, L, mid);
work(l + l1, r, mid + 1, R);
}
int main() {
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
q[++num] = (node){0, i, a[i], 0, 0, 0};
}
for (int i = 1; i <= m; i++) {
op = getchar();
while (op != 'C' && op != 'Q') op = getchar();
if (op == 'Q') {
scanf("%d %d %d", &x, &y, &k);
q[++num] = (node){++tot, x, y, k, 1, 0};
}
else {
scanf("%d %d", &x, &y);
q[++num] = (node){0, x, a[x], 0, 2, 0};
a[x] = y;
q[++num] = (node){0, x, a[x], 0, 0, 0};
}
}
work(1, num, 0, 2e9);
for (int i = 1; i <= tot; i++) printf("%d\n", ans[i]);
return 0;
}