[COCI2015]COCI
题目大意：
有\(n(n\le5\times10^5)\)个人比赛，比赛总共进行\(3\)轮，每一轮得分为\([0,650]\)内的整数。现在已经得知每个人前两轮的成绩。若规定一个人\(A\)在前两轮的成绩均严格高于\(B\)，则\(A\)在第\(3\)轮的成绩也一定高于\(B\)。求每个人在比赛完成后，最高及最低的可能排名。
思路：
以最高排名为例，对于人\(A\)来言，若\(B\)在前两轮得分的总和\(-A\)在前两轮得分的总和\(\ge 650\)，则无论如何，\(A\)都没有再次超过\(B\)的可能。
剩下我们则需要统计与\(A\)两轮得分差值不超过\(650\)，但是又全面碾压\(A\)的人的个数。这显然是一个二维数点问题，用二维树状数组解决即可。
时间复杂度\(\mathcal O(n\log^2650)\)。
源代码：
#include<cstdio>
#include<cctype>
#include<algorithm>
inline int getint() {
register char ch;
while(!isdigit(ch=getchar()));
register int x=ch^'0';
while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');
return x;
}
const int N=5e5+1,M=652;
struct Player {
int a,b,id;
int total() const {
return a+b;
}
bool operator < (const Player &rhs) const {
return total()<rhs.total();
}
};
Player p[N];
class FenwickTree1 {
private:
int val[M][M];
int lowbit(const int &x) const {
return x&-x;
}
public:
void modify(int p,const int &q,const int &x) {
for(;p;p-=lowbit(p)) {
for(register int j=q;j;j-=lowbit(j)) {
val[p][j]+=x;
}
}
}
int query(int p,const int &q) {
int ret=0;
for(;p<M;p+=lowbit(p)) {
for(register int j=q;j<M;j+=lowbit(j)) {
ret+=val[p][j];
}
}
return ret;
}
};
FenwickTree1 t1;
class FenwickTree2 {
private:
int val[M][M];
int lowbit(const int &x) const {
return x&-x;
}
public:
void modify(int p,int q,const int &x) {
for(p++,q++;p<M;p+=lowbit(p)) {
for(register int j=q;j<M;j+=lowbit(j)) {
val[p][j]+=x;
}
}
}
int query(int p,int q) {
int ret=0;
for(p++,q++;p;p-=lowbit(p)) {
for(register int j=q;j;j-=lowbit(j)) {
ret+=val[p][j];
}
}
return ret;
}
};
FenwickTree2 t2;
int max[N],min[N];
int main() {
const int n=getint();
for(register int i=1;i<=n;i++) {
p[i].a=getint();
p[i].b=getint();
p[i].id=i;
}
std::sort(&p[1],&p[n]+1);
for(register int i=1,j=1;i<=n;i++) {
for(;j<=n&&p[j].total()-p[i].total()<=650;j++) {
t1.modify(p[j].a,p[j].b,1);
}
max[p[i].id]=n-j+1+t1.query(p[i].a+1,p[i].b+1);
t1.modify(p[i].a,p[i].b,-1);
}
std::reverse(&p[1],&p[n]+1);
for(register int i=1,j=1;i<=n;i++) {
for(;j<=n&&p[i].total()-p[j].total()<650;j++) {
t2.modify(p[j].a,p[j].b,1);
}
min[p[i].id]=n-(n-j+1+t2.query(p[i].a-1,p[i].b-1));
}
for(register int i=1;i<=n;i++) {
printf("%d %d\n",max[i]+1,min[i]);
}
return 0;
}