Codeforces Technocup 2020 - Elimination Round 3 D2. Optimal Subsequences (Hard Version) 二分+树状数组

## 代码

```#include <bits/stdc++.h>
using namespace std;
const int maxn = 200005;
int n,m;
int a[maxn];
int c[maxn];
int lowbit(int x){
return x & -x;
}
void update(int pos,int x){
while(pos <= n){
c[pos] += x;
pos += lowbit(pos);
}
return;
}
int val(int pos){
int ret = 0;
while(pos > 0){
ret += c[pos];
pos -= lowbit(pos);
}
return ret;
}
struct num{
int id;
int val;
}b[maxn];
bool cmp(num x,num y){
return x.val > y.val || (x.val == y.val && x.id < y.id);
}
struct query{
int pos,k,id;
}q[maxn];
bool cmp2(query x,query y){
return (x.pos < y.pos) || (x.pos == y.pos && x.k < y.k);
}
int ans[maxn];
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n;
for(int i = 1;i <= n;++i){
cin >> a[i];
b[i].val = a[i];
b[i].id = i;
}
sort(b+1,b+n+1,cmp);
cin >> m;
for(int i = 1;i <= m;++i){
cin >> q[i].pos >> q[i].k;
q[i].id = i;
}
sort(q+1,q+m+1,cmp2);
int l,r,mid;
int now = 0;
for(int i = 1;i <= m;++i){
while(now < q[i].pos){
now++;
update(b[now].id,1);
}
l = 1;r = n;
int d = 0;
while(l <= r){
mid = (l + r) >> 1;
int x = val(mid);
if(x >= q[i].k){
d = mid;
r = mid - 1;
}
else l = mid + 1;
}
ans[q[i].id] = a[d];
}
for(int i = 1;i <= m;++i){
cout << ans[i] << "\n";
}
return 0;
}```

0 条评论