这题本来是树状数组的例题，我就是用线段树（我用不来树状数组）。
第一次应用线段树做这种优化，洛谷的拦截导弹优化应该也可以这样做。
题目中Y坐标已经排好序，所以只要看第 i 个结点前面有几个结点 X 比 X[i]小。
如果和拦截导弹那样O(N2)，在这题显然不行。
<1>第一种想法：
先建树，维护1~N号结点的最大值，然后 for i=1 to N 每次查询区间（1，i-1），如果访问区间在查询期间内且最大值小于等于X[i]，那么ans+=(l-r+1)。
但是我超时了，60分，因为这种查询没有最大利用到线段树的作用--能-直接查询到整个区间的有效信息就更新。
<2>第二种想法：
不用建树，维护1~MAX { X[i] }区间各个X的值的个数，然后 for i=1 to N 每次先查询( 1，X[i] )，这样可以查询到之前的点有几个小于等于当先X的点了，
由于自己不能算上去，所以先查询再插入，给sum[X[i]]+1，这样较为合理应用了线段树的神威。还有值得注意的是0，由于我懒得想0开头的线段树，0额外
算就是了。具体见AC代码。
[AC代码]
#include<bits/stdc++.h> using namespace std; int sum[500005],u[100005],ans,ll=1,rr,fa,n;//ll是左端点，不用变来变去，所以下面没有判断左端点的语句，fa记录0的个数，具体处理应该不难理解。 void ask(int t,int l,int r) { if(r<=rr) { ans+=sum[t]; return; } int mid=l+r>>1; ask(t*2,l,mid); if(rr>mid) ask(t*2+1,mid+1,r); return; } void charu(int t,int l,int r) { if(l==r) { sum[t]++; // printf("插入成功:X=%d ",rr); return; } int mid=l+r>>1; if(rr<=mid) charu(t*2,l,mid); else charu(t*2+1,mid+1,r); sum[t]=sum[t*2]+sum[t*2+1]; return; } int main() { scanf("%d",&n); int a,b; for(int i=1;i<=n;i++) { ans=0; scanf("%d%d",&a,&b); if(a==0) {u[fa++]++;continue;}//0单独处理 rr=a; ask(1,1,32000); u[ans+fa]++; charu(1,1,32000); } for(int i=0;i<n;i++) printf("%d ",u[i]); return 0; }