这题本来是树状数组的例题，我就是用线段树（我用不来树状数组）。

第一次应用线段树做这种优化，洛谷的拦截导弹优化应该也可以这样做。

题目中Y坐标已经排好序，所以只要看第 i 个结点前面有几个结点 X 比 X[i]小。

如果和拦截导弹那样O(N²)，在这题显然不行。

<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
     
      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\n",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