P8065 题解

y0y68 · 2022-02-01 20:04:09 · 题解

显然离线处理，将询问和球员分别按照年龄排序，然后依次处理询问的时候先每次添加当前可行的球员的 skill 值。然后根据贪心，将当前已经添加的球员的 skill 值从大到小排序，然后隔一个选一个即可，时间复杂度 O(mn \log n)。

主要问题在于如何去快速维护球员的 skill 值。

考虑使用线段树，预处理出每个球员 skill 值是所有球员中第几小的（注意不要去重），记为 id，每个节点记录以下信息（设该节点范围为 [l,r]，下面所谓“选 x”表示选取 id 为 x 的球员）：

于是就可以写出 push_up 操作：

inline Node push_up(int u,int v){
    Node ret;
    ret.ch[0]=tree[u].ch[tree[v].ch[0]];
    ret.ch[1]=tree[u].ch[tree[v].ch[1]];
    ret.cnt[0]=tree[v].cnt[0]+tree[u].cnt[tree[v].ch[0]];
    ret.cnt[1]=tree[v].cnt[1]+tree[u].cnt[tree[v].ch[1]];
    ret.val[0]=tree[v].val[0]+tree[u].val[tree[v].ch[0]];
    ret.val[1]=tree[v].val[1]+tree[u].val[tree[v].ch[1]];
    return ret;
}

然后就是线段树板子了，时间复杂度 O((n+m)\log n)。

代码如下：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=3e5+5;
int n,m,dy[N];ll ans[N];
struct Node{
    int ag,sk,id;
    bool operator < (const Node &rhs) const{
        return ag<rhs.ag;
    }
}a[N];
bool cmp(Node _1,Node _2){
    return _1.sk<_2.sk;
}
struct Query{
    int ag,nm,id;
    bool operator < (const Query &rhs) const{
        return ag<rhs.ag;
    }
}q[N];
struct Segment_Tree{
    struct Node{
        bool ch[2];
        int cnt[2];ll val[2];
    }tree[N<<2];
    inline int ls(int u){return u<<1;}
    inline int rs(int u){return u<<1|1;}
    inline Node push_up(int u,int v){
        Node ret;
        ret.ch[0]=tree[u].ch[tree[v].ch[0]];
        ret.ch[1]=tree[u].ch[tree[v].ch[1]];
        ret.cnt[0]=tree[v].cnt[0]+tree[u].cnt[tree[v].ch[0]];
        ret.cnt[1]=tree[v].cnt[1]+tree[u].cnt[tree[v].ch[1]];
        ret.val[0]=tree[v].val[0]+tree[u].val[tree[v].ch[0]];
        ret.val[1]=tree[v].val[1]+tree[u].val[tree[v].ch[1]];
        return ret;
    }
    inline void update(int u,int l,int r,int p,int x){
        if(l==r){
            tree[u].ch[0]=tree[u].cnt[0]=1;
            tree[u].val[0]=x;return;
        }
        int mid=l+r>>1;
        if(mid>=p)update(ls(u),l,mid,p,x);
        else update(rs(u),mid+1,r,p,x);
        tree[u]=push_up(ls(u),rs(u));
    }
    inline ll query(int u,int l,int r,int x,bool key){
        if(l==r)return tree[u].val[key];
        int mid=l+r>>1;
        if(tree[rs(u)].cnt[key]>=x)return query(rs(u),mid+1,r,x,key);
        return tree[rs(u)].val[key]+query(ls(u),l,mid,x-tree[rs(u)].cnt[key],tree[rs(u)].ch[key]);
    }
}t;
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)
        scanf("%d%d",&a[i].ag,&a[i].sk),a[i].id=i;
    sort(a+1,a+n+1,cmp);
    for(int i=1;i<=n;i++)
        dy[a[i].id]=i;
    sort(a+1,a+n+1);
    cin>>m;
    for(int i=1;i<=m;i++)
        scanf("%d%d",&q[i].ag,&q[i].nm),q[i].id=i;
    sort(q+1,q+m+1);
    for(int i=1,j=1;i<=m;i++){
        while(j<=n&&a[j].ag<=q[i].ag)
            t.update(1,1,n,dy[a[j].id],a[j].sk),j++;
        ans[q[i].id]=t.query(1,1,n,q[i].nm,0);
    }
    for(int i=1;i<=m;i++)
        printf("%lld\n",ans[i]);
    return 0;
}