自动搬运

查看原文

来自洛谷，原作者为

	muyang_233 enfj|阔耐的蓝孩纸|MOer/OIer

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

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

以下是正文

原题传送门

根据题意，我们知道，对于一个选手 $A$，如果选手 $B$ 的前两轮分数都高于 $A$，那么 $B$ 的排名肯定高于 $A$；同样的，如果选手 $B$ 的前两轮分数都低于 $A$，那么 $B$ 的排名肯定低于 $A$。
所以对于每个选手 $A$，我们只需统计两轮分数都高于/低于 $A$ 的选手个数，然后再进行计算即可。

但是，本题中分数相同的选手排名相同。

所以，在统计完上面的情况后，我们要注意：对于两个选手，若分数分别为 $A(x,0)$ 和 $B(x,650)$，那么实际上 $B(x,650)$ 的最低排名等于 $A(x,0)$ 的最高排名。
这是容易证明的：考虑极端情况，$B$ 如果最后一轮得 $0$ 分，而 $A$ 最后一轮得 $650$ 分，那么他们的分数也持平。而其他情况下 $B$ 的排名肯定不会更差。

而剩下的情况中，既不存在有一人两轮分数都较高的两个选手，也不存在上面的特殊情况，可以证明，他们的排名考虑上面的统计方法即可。（仍然使用极端情况证明。）

现在我们来考虑怎么统计。

我们不妨对第一轮分数排序，然后对于第二轮分数，使用树状数组维护即可。

具体地，对于一个选手 $A(a,b)$，考虑所有第一轮分数严格大于 $A(a,b)$ 的选手 $B$，用他们的第二轮分数更新树状数组即可。小于同理。

代码如下：

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=651;
struct NODE{
	int x,y,id;
}in[500005];
int n;
int c[1005];
int ans1[500005];
int ans2[500005];
int cnt[maxn+5][maxn+5];
inline void input(int &x){
	x=0;char ch=getchar();
	while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
	int p=1;if (ch=='-') p=-1,ch=getchar();
	while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();x*=p;
}
void write(int x){
	if (x<10){
		putchar((char)(x+'0'));return;
	}
	write(x/10);
	putchar((char)(x%10+'0'));
}
inline void output(int x,char c){
	if (x<0) {putchar('-');x*=-1;}
	write(x);putchar(c);
}
bool cmp(NODE _1,NODE _2){//排序
	return _1.x^_2.x?_1.x>_2.x:_1.y>_2.y;
}
int lowbit(int x){
	return x&(-x);
}
inline void update(int p){
	while(p<=maxn){
		++c[p];
		p+=lowbit(p);
	}
}
inline int query(int p){
	int res=0;
	while(p>0){
		res+=c[p];
		p-=lowbit(p);
	}
	return res;
}
int main(){
	freopen("compete.in","r",stdin);
	freopen("compete.out","w",stdout);
	input(n);
	for (int i=1;i<=n;i++){
		input(in[i].x);input(in[i].y);
		++in[i].x;++in[i].y;//为了树状数组写的方便，这里加个1
		in[i].id=i;++cnt[in[i].x][in[i].y];
	}
	sort(in+1,in+n+1,cmp);//排序
	int p=0;//记录上一个第一轮分数不同的位置
	for (int i=1;i<=n;i++){
		int now=query(in[i].y);//第一轮分数大于，第二轮分数小于等于i的选手个数
		int now1=p-now;//用第一轮分数大于i的选手总数减去now，就是两轮分数都大于i的选手个数
		ans1[in[i].id]=now1+1;//now1个选手比i分数高，i至少是(now1+1)名
		if (in[i].x!=in[i+1].x){//第一轮分数出现不同，更新树状数组
			while(p<i){
				update(in[++p].y);//更新
			}
		}
	}
	memset(c,0,sizeof(c));
	int q=n+1;//记录上一个第一轮分数不同的位置
	for (int i=n;i>0;i--){
		int now2=query(in[i].y-1);//两轮分数都小于i的选手个数
		ans2[in[i].id]=n-now2;//now2个选手比i分数低，i至多是(n-now2)名
		if (in[i].x==maxn) ans2[in[i].id]-=cnt[1][in[i].y];//特殊情况：650的可以被0的追平
		if (in[i].y==maxn) ans2[in[i].id]-=cnt[in[i].x][1];//特殊情况：650的可以被0的追平
		if (in[i].x!=in[i-1].x){//第一轮分数出现不同，更新树状数组
			while(q>i){
				update(in[--q].y);//更新
			}
		}
	}
	for (int i=1;i<=n;i++){//输出
		output(ans1[i],' ');output(ans2[i],'\n');
	}
	return 0;
}```