【題目敘述】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";
}
}