跃迁引擎启动

Codeforces 1181D Irrigation 题解

发表于 更新于 分类于 ， 阅读次数：

题面

有 $m$ 个城市，每天选举办祭典次数最少且标号最小的的城市举办祭典，已知前 $n$ 天的举办情况，询问 $q$ 次第 $k$ 天的举办城市。

其中 $1 \le n, m, q \le 5\times 10^5, n+1 \le k \le 10^{18}$。

分析

处理出前 $n$ 天每个城市的举办情况，按照举办次数排序，将这个函数想象成水槽，发现之后的每天其实就是在这个类似阶梯的函数上注水。

如果知道当前位置的所处的注水高度和长度，将询问值减掉底下的面积并对长度取模，转化成询问这部分标号的第 $k$ 大。

因此，我们离线询问，维护当前水槽底部的面积和下一个台阶的整体面积。

代码

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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <utility>
#define ms(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
typedef pair<ll,int> PLI;
const int mod = 998244353;
const int inf = 1 << 30;
const int maxn = 500000 + 5;

struct fhqTreap {
    int ch[maxn][2], key[maxn], rnd[maxn], size[maxn], root, tot;
    fhqTreap() { root = tot = 0; }
    void clear() { root = tot = 0; }
    int node(int v) {
        key[++tot] = v; rnd[tot] = rand();
        size[tot] = 1;
        ch[tot][0] = ch[tot][1] = 0;
        return tot;
    }
    void pushup(int x) { size[x] = size[ch[x][0]] + size[ch[x][1]] + 1; }
    void split(int now, int k, int &x, int &y) {
        if (!now) {
            x = y = 0; return;
        }
        if (key[now] <= k) {
            x = now;
            split(ch[now][1], k, ch[now][1], y);
        } else {
            y = now;
            split(ch[now][0], k, x, ch[now][0]);
        }
        pushup(now);
    }
    int merge(int x, int y) {
        if (x == 0 || y == 0) return x + y;
        if (rnd[x] < rnd[y]) {
            ch[x][1] = merge(ch[x][1], y);
            pushup(x); return x;
        } else {
            ch[y][0] = merge(x, ch[y][0]);
            pushup(y); return y;
        }
    }
    void insert(int v) {
        int x = 0, y = 0;
        split(root, v, x, y);
        root = merge(merge(x, node(v)), y);
    }
    void del(int v) {
        int x = 0, y = 0, z = 0;
        split(root, v, x, z);
        split(x, v - 1, x, y);
        y = merge(ch[y][0], ch[y][1]);
        root = merge(merge(x, y), z);
    }
    int find(int v) {
        int x = 0, y = 0;
        split(root, v - 1, x, y);
        int ans = size[x] + 1;
        root = merge(x, y);
        return ans;
    }
    int findx(int now, int rank) {
        while (true) {
            if (size[ch[now][0]] >= rank) now = ch[now][0];
            else if (size[ch[now][0]] + 1 == rank) return key[now];
            else {
                rank -= size[ch[now][0]] + 1;
                now = ch[now][1];
            }
        }
    }
    int findx(int rank) { 
        return findx(root, rank); 
    }
} f;

int n, m, q, b[maxn], ans[maxn];
PII a[maxn];
PLI que[maxn];

int main() {
    scanf("%d%d%d", &n, &m, &q);
    for (int i = 1; i <= m; i++) a[i].second = i;
    for (int i = 1; i <= n; i++) {
        scanf("%d", b + i);
        a[b[i]].first++;
    }
    sort(a + 1, a + 1 + m);
    for (int i = 1; i <= q; i++) scanf("%I64d", &que[i].first), que[i].second = i;
    sort(que + 1, que + 1 + q);
    
    int p = 0;
    ll last = 0, nxt = n;
    for (int i = 1; i <= q; i++) {
        ll tot = que[i].first;
        while (tot > nxt && p < m) {
            int x = a[p].first, st = p + 1;
            while (p < m && a[st].first == a[p + 1].first) {
                f.insert(a[++p].second);
            }
            last = nxt;
            if (p < m) nxt += 1ll * p * (a[p + 1].first - a[p].first);
        }
        tot -= last + 1;
        ans[que[i].second] = f.findx(tot % p + 1);
    }
    for (int i = 1; i <= q; i++) printf("%d\n", ans[i]);
    return 0;
}