一开始做这题我是懵逼的，然后看了题解才懂。题目里有两个重要条件不能忽视，一个是给出的数据是以y为第一优先级，x为第二优先级给出来的，第二个是xy都是有范围的。 那么首先我们很容易想到这个算法：对每一个点（x0，y0），去找在他前面的点中的横坐标小于x0的有几个。这个算法的正确性是无需置疑的，因为数据是以y为第一优先级，x为第二优先级给出来的。 那么，问题就是，怎么实现这个算法呢？观察到第二个重要条件，x，y是有界的。 有界，我们可以想到什么呢？我想到一个问题，就是给了很多范围在1到100的数，让你排序。我们只要用num数组记录一下每个数出现的次数就好了。（这道题的统计也用到了这种方法）。这种方法的核心是四个字，维度变换。 我们再想，小于3的x，是不是等于等于1的x+等于2的x的总和?这是不是有点像sum？ 到这里，算法就出来了。
#include<cstdio> #include<iostream> #include<queue> #include<algorithm> #include<cmath> #include<vector> #include<cstring> using namespace std; const int maxn=32005; int n,tree[maxn],num[maxn]; int lowbit(int x) { return(x&(-x)); } void add(int k) { while(k<=maxn) { tree[k]++; k+=lowbit(k); } } int read(int k) { int sum=0; while(k) { sum+=tree[k]; k-=lowbit(k); } return sum; } int main(void) { int x,y; while(cin>>n) { memset(tree,0,sizeof(tree)); memset(num,0,sizeof(num)); for(int i=1;i<=n;i++) { scanf("%d%d",&x,&y); x++; num[read(x)]++; add(x); } for(int i=0;i<n;i++) printf("%d\n",num[i]); } /* for(int i=1;i<=7;i++) { printf("%d:%d\n",i,read(i)); } */ return 0; }