自动搬运

查看原文

来自洛谷，原作者为

	y0y68 AFO

搬运于2025-08-24 22:35:38，当前版本为作者最后更新于2022-02-01 20:04:09，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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

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

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

• $ch_0$：表示若 $r+1$ 不选，则 $l$ 选还是不选，不选为 $0$，选为 $1$。
• $ch_1$：表示若 $r+1$ 选，则 $l$ 选还是不选，不选为 $0$，选为 $1$。
• $cnt_0$：表示若 $r+1$ 不选，则 $[l,r]$ 中选几个。
• $cnt_1$：表示若 $r+1$ 选，则 $[l,r]$ 中选几个。
• $val_0$：表示若 $r+1$ 不选，则在 $[l,r]$ 中选可以获得的最大优秀程度。
• $val_1$：表示若 $r+1$ 选，则在 $[l,r]$ 中选可以获得的最大优秀程度。

于是就可以写出 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;
}