Codeforces 1181D (树状数组)

考虑将每个国家的举行次数排序，然后按顺序离线去做即可，可以看代码注释方法。
注意要求$k$大，可以Splay，但是可以更方便的用树状数组来求

知识点：
1、思维要清晰

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<map>
#include<queue>
#include<set>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;

namespace flyinthesky {

    const LL MAXN = 500000 + 5;

    LL n, m, q;
    LL qID[MAXN], k[MAXN];
    LL H[MAXN], Hid[MAXN];
    LL ans[MAXN], C[MAXN];

    LL cmpH(LL a, LL b) {return H[a] < H[b];}
    LL cmpq(LL a, LL b) {return k[a] < k[b];}

    void update(LL x) {while (x <= m) C[x]++, x += x & (-x);}
    LL query(LL x) {
        LL p = 0;
        for (LL i = 20; ~i; --i) {
            if (p + (1 << i) <= m && C[p + (1 << i)] <= x) x -= C[p + (1 << i)], p += (1 << i);
        }
        return p;
    }

    void clean() {
    }
    int solve() {

        clean();
        cin >> n >> m >> q;

        for (LL x, i = 1; i <= n; ++i) scanf("%lld", &x), ++H[x];
        for (LL i = 1; i <= m; ++i) Hid[i] = i;
        sort(Hid + 1, Hid + 1 + m, cmpH);

        for (LL i = 1; i <= q; ++i) scanf("%lld", &k[i]), k[i] -= n, qID[i] = i;
        sort(qID + 1, qID + 1 + q, cmpq);

        LL now = 1, gg = 0; // gg 为当前累加值
        update(Hid[1]);
        for (LL i = 1; i <= q; ++i) {
            LL v = k[qID[i]];
            while (now < m && gg + now * (H[Hid[now + 1]] - H[Hid[now]]) < k[qID[i]]) gg += now * (H[Hid[now + 1]] - H[Hid[now]]), update(Hid[++now]);
            v -= gg + 1;
            v %= now;
            ans[qID[i]] = query(v) + 1;
        }

        for (LL i = 1; i <= q; ++i) printf("%lld\n", ans[i]);

        return 0;
    } 
}
int main() {
    flyinthesky::solve();
    return 0;
}