传送门
由于输出中的y还是单调递增，甚至还不用排序了。
我们用树状数组维护一个类似桶的东西即可，在update，注意是i=x;i<=32000，而不是n
另外，由于x有可能为0，注意lowbit(0)会炸掉，因此给x++来避免特判。
#include<iostream> #include<cstdio> #include<cstring> using namespace std; int n,tree[32015],level[32015]; inline int lowbit(int x) { return x&(-x); } inline void update(int x,int delta) { for(int i=x;i<=32010;i+=lowbit(i)) { tree[i]+=delta; } } inline int query(int x) { int sum=0; for(int i=x;i>0;i-=lowbit(i)) { sum+=tree[i]; } return sum; } int main() { int x,y; while(scanf("%d",&n)!=EOF) { memset(tree,0,sizeof(tree)); memset(level,0,sizeof(level)); for(int i=1;i<=n;i++) { scanf("%d%d",&x,&y); x++; level[query(x)]++; update(x,1); } for(int i=0;i<n;i++) cout<<level[i]<<endl; } return 0; }转载于:https://www.cnblogs.com/Patrickpwq/articles/9419794.html
