y从小到大排序，y相同，x按从小到大排序，当然，输入顺序就是这么输入，不用排了，唯一的坑是x从0开始，要树状数组从1开始，x要加一，否则越界，但是为什么给我显示tle？？？？
#include <iostream> #include <cstring> #include <cstdio> #include <algorithm> using namespace std; const int maxn=15000+1000; int s[35000],ans[maxn]; int n; void add(int x,int v) { for(int i=x;i<=32001;i+=i&-i) s[i]+=v; } int sum(int x) { int sum=0; for(int i=x;i>0;i-=i&-i) sum+=s[i]; return sum; } int main() { while(~scanf("%d",&n)) { memset(s,0,sizeof(s)); memset(ans,0,sizeof(ans)); int xx,yy; for(int i=1;i<=n;i++) { scanf("%d%d",&xx,&yy); add(xx+1,1);//防止越界 int nn=sum(xx+1); nn=nn-1; ans[nn]++; } for(int i=0;i<n;i++) printf("%d\n",ans[i]); } return 0; }
转载于:https://www.cnblogs.com/Wangwanxiang/p/7268025.html
