P4812 [COCI2014-2015#3] COCI の Solution

· · 题解

原题传送门

根据题意，我们知道，对于一个选手 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;
}```