为了实现和 Sonochi Sonochi的约定， Washi Washi必须要打败眼前强大的怪物。 怪物分布在二维平面上， 某个怪物的 rank rank被定义为 x x坐标不大于其 x x坐标，且 y y坐标不大于其 y y坐标的怪物的数量。（不含其自身） Washi Washi要你输出 n n行，每行一个整数，分别代表 rank rank为 0 0~ n−1 n−1的怪物数量。
Input输入第一行为一个正整数 n n， 接下来 n n行，第 i i行两个整数 xi xi、 yi yi，表示一个怪物的坐标。 保证输入的坐标两两不同。
Output包含 n n行，每行一个整数，第 i i行的数代表 rank rank为 i−1 i−1的怪物数量。
思路：以X为首要优先级，Y为次要优先级sort排序后，对于i的来说xj<=xi（j<=i)的，只需要知道小于等于yi的个数。
#include <iostream> #include <stdio.h> #include <map> #include <algorithm> #include <string.h> using namespace std; const int AX = 1e5+666; int rankkk[AX]; const int n = AX; struct Node { int x; int y; }node[AX]; bool cmp(const Node &a,const Node &b){ if(a.x!=b.x){ return a.x<b.x; }else{ return a.y<b.y; } } int v[AX]; int lowbit(int x){ return x&(-x); } void update(int value,int site){ while(site<AX){ v[site] += value; site += lowbit(site); } } int getsum(int i){ int sum = 0; while(i>=1){ sum += v[i]; i -= lowbit(i); } return sum; } int main(){ memset(rankkk,0,sizeof(rankkk)); int m; cin>>m; for(int i=0;i<m;i++){ scanf("%d%d",&node[i].x,&node[i].y); } sort(node,node+m,cmp); for(int i=0;i<m;i++){ rankkk[getsum(node[i].y)]++; update(1,node[i].y); } for(int i=0;i<m;i++){ printf("%d\n",rankkk[i]); } return 0; }
