题目链接：弱弱的战壕

这道题似乎是vijos上能找到的最简单的树状数组题了。

原来，我有一个错误的思想，我的设计是维护两个树状数组，一个是横坐标，一个是纵坐标，然后读入每个点的坐标，扔进对应的树状数组内，然后计算时，只要以当前点的坐标为末点求前缀和，在两个前缀和中取最小的一个即可。

但是这个想法很明显有错误比如如图的状况：



此时，在计算1点时，两个的前缀和均为1，但事实上，1点能保护的点为0个。

那么我们应该怎么去解这道题呢？

其实也很简单，我们只维护一个树状数组，

首先我们先把点排序，以y为主关键字，x为副关键字，从小到大排序。

然后我们从排序后的第一个点开始计算，我们求一下以当前点的x坐标为末点的前缀和，这就是当前保护的数量，然后在把当前的这个x坐标扔进树状数组。

为什么这么做是正确的？

这很简单，求x的前缀和，保证得出的都是小于x的点，而按y的顺序枚举，横坐标大于等于当前y的点还没放入（我们是计算完才放入的），这样就保证了我们得出的数是我们期望求的。

代码如下：

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

int xvis[32002];

int n;

struct point{

    int x,y;

};

int cmp(point a,point b){

    if(a.y!=b.y){

        return a.y<b.y;

    }else{

        return a.x<b.x;

    }

}

point pp[32002];

int lowbit(int x){

    return x&(-x);

}

void add(int x,int p){

    while(x<=32000){

        xvis[x]+=p;

        x+=lowbit(x);

    }

}

int sum(int x){

    int ans=0;

    while(x>0){

        ans+=xvis[x];

        x-=lowbit(x);

    }

    return ans;

}

int vis[15001];

int main(){

    memset(xvis,0,sizeof(xvis));

    scanf("%d",&n);

    for(int i=0;i<n;i++){

        scanf("%d%d",&pp[i].x,&pp[i].y);

    }

    memset(vis,0,sizeof(vis));

    sort(pp,pp+n,cmp);

    for(int i=0;i<n;i++){

        int ans=sum(pp[i].x);

        add(pp[i].x,1);

        vis[ans]++;

    }

    for(int i=0;i<n;i++){

        printf("%d",vis[i]);

        if(i!=n-1){

            printf("\n");

        }

    }

    return 0;

}