Codeforces Technocup 2020 - Elimination Round 3 D2. Optimal Subsequences (Hard Version) 二分+树状数组
树状数组 二分   发布于 2019-11-25   501人围观  0条评论
树状数组 二分   发表于 2019-11-25   501人围观  0条评论

题目大意

给定一个序列,每次询问参数为pos和k,求问长度为pos的和最大的子序列中第k个元素是什么。

题解

这题其实有一个easy version,用map稍微搞一搞就能过那种

然后这题数据范围到2e5了,就不能用map乱搞了。

首先我们要想一下如何构造这个长为pos且和最大的子序列怎么构造呢?

我们只要对原序列从大到小排一次序,且保证在等大的时候原序列中靠前的元素在排序后也考前,然后我们只需要从排序后的序列中取前pos个数,就是符合要求的子序列了。

但是询问次数过多,我们就不能对于每一个request都重新求一次符合要求的子序列。

我们发现这个序列是递增的,就是如果pos[i] > pos[j],那么询问i的序列一定就是询问j的序列再接上一段。

于是我们将询问也按照pos从小到大排序。

但是我们怎么找这个子序列中第k个元素是多少呢?

我们在对原序列进行排序的时候同时记录下元素在原序列中的位置,然后在选序列的时候,可以用这样一种经典的记录方式:

将当前被选中的元素加入树状数组进行计数,即将该元素对应的原序列的位置在树状数组上的位置进行update(pos,1)

当我们询问的时候,从1——n进行二分,统计在这个位置mid之前的选中数一共有多少个。

最终二分出来的答案就代表着选中序列第k位在原数组中的位置了。直接去原数组中找就可以了。

代码

#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;
}


上一篇: 二分图最大匹配KM算法之BFS版本模板

下一篇: 可持久化并查集 洛谷P3401

立即登录,发表评论
没有帐号?立即注册
0 条评论