题目链接：https://loj.ac/problem/10114 解题思路 二维树状数组模板题，只用到单点更新区间查询，首先离散化，然后二维树状数组我开的是map，因为不知道具体矩阵的长宽，所以开15000*15000会MLE。然后就是二维数组的模板了，按顺序先查询后更新即可。其实，因为是按y增序和x增序来的，所以没必要离散化和二维树状数组，一维树状数组可以很好的解决。 AC代码
#include <iostream> #include <stdio.h> #include <cstring> #include <algorithm> #include <vector> #include <map> using namespace std; const int N=15005; int n; int X[N],Y[N]; int cnt1,cnt2; int siz1,siz2; struct node { int x,y; }a[N]; map<int,map<int,int > >sum; int lowbit(int x) { return x&-x; } void update(int x,int y) { while(x<=siz1) { int yy=y; while(yy<=siz2) { sum[x][yy]++; yy+=lowbit(yy); } x+=lowbit(x); } } int query(int x,int y) { int res=0; while(x) { int yy=y; while(yy) { res+=sum[x][yy]; yy-=lowbit(yy); } x-=lowbit(x); } return res; } int ans[N]; int main() { scanf("%d",&n); for(int i=1;i<=n;++i) { scanf("%d%d",&a[i].x,&a[i].y); X[++cnt1]=a[i].x; Y[++cnt2]=a[i].y; } sort(X+1,X+1+cnt1); siz1=unique(X+1,X+1+cnt1)-X-1; siz2=unique(Y+1,Y+1+cnt2)-Y-1; for(int i=1;i<=n;++i) { int tmp_x=lower_bound(X+1,X+1+siz1,a[i].x)-X; int tmp_y=lower_bound(Y+1,Y+1+siz2,a[i].y)-Y; int rank=query(tmp_x,tmp_y); ans[rank]++; update(tmp_x,tmp_y); } for(int i=0;i<n;++i) { printf("%d\n",ans[i]); } return 0; }