DDOSvoid's Blog

Luogu P2617 Dynamic Rankings(整体二分)

发表于 分类于
本文字数： 1.9k 阅读时长 ≈ 2 分钟

题目描述

https://www.luogu.com.cn/problem/P2617

Solution

带修版本的区间第 $k$ 小，我们把修改换成插入和删除，然后将修改和查询一起二分即可

时间复杂度 $O(n\log^2 n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#define maxn 200010
#define maxm 400010
#define lowbit(i) ((i) & (-i))
#define INF 1000000000
using namespace std;

int n, m, a[maxn];

struct Query {
    int opt, l, r, k, id; // -1 add 1 del 0 query
} Q[maxm], t1[maxm], t2[maxm]; int cnt;

int Bit[maxn];
void add(int i, int v) { while (i <= n) Bit[i] += v, i += lowbit(i); }

int get_sum(int i) {
    int s = 0;
    while (i) s += Bit[i], i -= lowbit(i);
    return s;
} 

int ans[maxn], cans;
void solve(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].id] = l;
        return ; 
    } int m = l + r >> 1, c1 = 0, c2 = 0; 
    for (int i = L; i <= R; ++i) {
        int opt = Q[i].opt, l = Q[i].l, r = Q[i].r, k = Q[i].k, v;
        if (opt == 0) {
            v = get_sum(r) - get_sum(l - 1);
            if (k <= v) t1[++c1] = Q[i];
            else t2[++c2] = Q[i], t2[c2].k -= v;
        }
        else {
            if (l <= m) t1[++c1] = Q[i], add(k, opt);
            else t2[++c2] = Q[i];
        }
    }
    for (int i = 1; i <= c1; ++i) add(t1[i].k, -t1[i].opt); 
    for (int i = 1; i <= c1; ++i) Q[L + i - 1] = t1[i];
    for (int i = 1; i <= c2; ++i) Q[L + c1 + i - 1] = t2[i];
    solve(l, m, L, L + c1 - 1); solve(m + 1, r, L + c1, R); 
} 


int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n >> m; cnt = n; 
    for (int i = 1; i <= n; ++i) cin >> a[i], Q[i] = { 1, a[i], 0, i, 0 }; 
    for (int i = 1; i <= m; ++i) {
        char s[3]; cin >> s + 1;
        if (s[1] == 'Q') {
            ++cnt; Q[cnt].opt = 0; Q[cnt].id = ++cans;
            cin >> Q[cnt].l >> Q[cnt].r >> Q[cnt].k;
        }
        else {
            int x, y; cin >> x >> y; 
            Q[++cnt] = { -1, a[x], 0, x, 0 };
            Q[++cnt] = { 1, y, 0, x, 0 }; a[x] = y; 
        }
    }
    solve(0, INF, 1, cnt);
    for (int i = 1; i <= cans; ++i) cout << ans[i] << "\n"; 
    return 0;
}