【題解】Codeforces 1181D. Irrigation

【題目敘述】http://codeforces.com/contest/1181/problem/D
【解題想法】線段樹,two-pointers

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
 
struct query{
    int idx;
    long long pos;
};
long long n, m, Q, cnt[500005], x, bit[500005], ans[500005];
map <long long, vector<int> > mp;
vector <query> q;
 
bool cmp(query x, query y){
    return x.pos < y.pos;
}
 
int sum(int x){
    int ret = 0;
    while (x){
        ret += bit[x];
        x -= x & (-x);
    }
    return ret;
}
 
int find(int x){
    int l = 0, r = m;
    while (r-l > 1){
        int mid = (r+l)/2;
        if (sum(mid) >= x) r = mid;
        else l = mid;
    }
    return r;
}
 
void update(int x){
    while (x <= m){
        bit[x]++;
        x += x & (-x);
    }
}
 
int main() {
    cin >> n >> m >> Q;
    for (int i = 0; i < n; i++){
        cin >> x;
        cnt[x]++;
    }
    for (int i = 1; i <= m; i++){
        mp[cnt[i]].push_back(i);
    }
    for (int i = 0; i < Q; i++){
        cin >> x;
        x -= n;
        q.push_back({i, x});
    }
    sort(q.begin(), q.end(), cmp);
    long long nxt = 0, h = (*mp.begin()).first, w = 0, cur_h = 0, cur = 0, nxt_q = 0;
    for (auto i:mp){
        nxt = cur + (i.first - cur_h)*w;
        while (nxt_q < Q && q[nxt_q].pos <= nxt){
            int target = (q[nxt_q].pos-cur) % w;
            if (target == 0) target = w;
            ans[q[nxt_q].idx] = find(target);
            nxt_q++;
        }
        cur = nxt;
        w += i.second.size();
        cur_h = i.first;
        for (auto j:i.second){
            update(j);
        }
    }
    while (nxt_q < Q){
        int target = (q[nxt_q].pos-cur) % w;
        if (target == 0) target = w;
        ans[q[nxt_q].idx] = find(target);
        nxt_q++;
    }
    for (int i = 0; i < Q; i++){
        cout << ans[i] << "\n";
    }
}
分享本文 Share with friends