题目链接：UESTC 1584 Washi与Sonochi的约定
题意：在二维平面上，某个点的ranked被定义为x坐标不大于其x坐标，且y坐标不大于其y坐标的怪物的数量。（不含其自身），要求输出n行，每行一个整数，分别代表rank为0~n^1的怪物数量。
分析：树状数组+排序，其实就是道树状数组的裸题，和poj2352是同题，套个板子就可以过
思路就是把所有的坐标读入之后，按照x为第优先级，y为第二优先级，都是从小到大排序，只从从0~n-1扫一遍，此时(i时)树状数组里的点的x值，
都不比val[i].x大，//这题所有坐标都不同。所以get(val[i].y)即可得到，所有x坐标不大于vali，且y坐标小于vali的坐标(点)的个数，
然后把val[i].y插入到树状数组里。扫一遍即可得到所有答案，复杂度 O(nlogn)！
下面给出AC代码：
1 #include <bits/stdc++.h> 2 using namespace std; 3 typedef long long LL; 4 const int MAXN=100010; 5 struct p 6 { 7 int x, y; 8 }val[MAXN]; 9 inline int read() 10 { 11 int x=0,f=1; 12 char ch=getchar(); 13 while(ch<'0'||ch>'9') 14 { 15 if(ch=='-') 16 f=-1; 17 ch=getchar(); 18 } 19 while(ch>='0'&&ch<='9') 20 { 21 x=x*10+ch-'0'; 22 ch=getchar(); 23 } 24 return x*f; 25 } 26 inline void write(int x) 27 { 28 if(x<0) 29 { 30 putchar('-'); 31 x=-x; 32 } 33 if(x>9) 34 { 35 write(x/10); 36 } 37 putchar(x%10+'0'); 38 } 39 inline bool cmp(const p &a,const p &b) 40 { 41 if(a.x!=b.x) return a.x<b.x; 42 else return a.y<b.y; 43 } 44 int ranked[MAXN<<1]; 45 int Tree[MAXN<<1]; 46 inline int lowbit(int x) 47 { 48 return (x&-x); 49 } 50 inline void add(int x,int value) 51 { 52 for(int i=x;i<MAXN;i+=lowbit(i)) 53 Tree[i]+=value; 54 } 55 inline int get(int x) 56 { 57 int res=0; 58 for(int i=x;i;i-=lowbit(i)) 59 { 60 res+=Tree[i]; 61 } 62 return res; 63 } 64 int main() 65 { 66 int n; 67 n=read(); 68 for(int i=0;i<n;i++) 69 { 70 scanf("%d%d",&val[i].x,&val[i].y); 71 } 72 sort(val,val+n,cmp); 73 for(int i=0;i<n;i++) 74 { 75 ranked[get(val[i].y)]++; 76 add(val[i].y, 1); 77 } 78 for(int i=0;i<n;i++) 79 printf("%d\n", ranked[i]); 80 cout<<endl; 81 return 0; 82 }
