描述 Description
永恒和 mx 正在玩一个即时战略游戏，名字嘛~~ 恕本人记性不好，忘了 -_-b。
mx 在他的基地附近建立了 n 个战壕，每个战壕都是一个独立的作战单位，射程可以达到无限（“mx 不赢定了？！？” 永恒 ftING…@_@）。
但是，战壕有一个弱点，就是只能攻击它的左下方，说白了就是横纵坐标都不大于它的点（mx：“我的战壕为什么这么菜”ToT）。这样，永恒就可以从别的地方进攻摧毁战壕，从而消灭 mx 的部队。
战壕都有一个保护范围，同它的攻击范围一样，它可以保护处在它左下方的战壕。所有处于它保护范围的战壕都叫做它的保护对象。这样，永恒就必须找到 mx 的战壕中保护对象最多的点，从而优先消灭它。
现在，由于永恒没有时间来计算，所以拜托你来完成这个任务：
给出这 n 个战壕的坐标 xi、yi，要你求出保护对象个数为 0，1，2……n-1 的战壕的个数。
输入格式 InputFormat
第一行，一个正整数 n（1<=n<=15000）
接下来 n 行，每行两个数 xi,yi，代表第 i 个点的坐标（1<=xi,yi<=32000）
注意：可能包含多重战壕的情况（即有数个点在同一坐标）
输出格式 OutputFormat
输出 n 行，分别代表保护对象为 0，1，2……n-1 的战壕的个数。
样例输入 SampleInput
5
1 1
5 1
7 1
3 3
5 5
样例输出 SampleOutput
1
2
1
1
0
代码 Code
将所有点按坐标排序，然后就可以转成一位树状数组来做。
#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int maxn=32005;
int i,j,t,n,m,l,r,k,z,y,x;
int tree[maxn],ans[maxn];
pair <int,int> a[maxn];
inline int lowbit(int s)
{
return s&(-s);
}
inline void ins(int s,int x)
{
while (s<=maxn)
{
tree[s]+=x;
s+=lowbit(s);
}
}
inline int sum(int s)
{
int t=0;
while (s>0)
{
t+=tree[s];
s-=lowbit(s);
}
return t;
}
int main()
{
scanf("%d",&n);
for (i=1;i<=n;i++) scanf("%d%d",&a[i].first,&a[i].second);
sort(a+1,a+n+1);
for (i=1;i<=n;i++)
{
ins(a[i].second,1);
ans[sum(a[i].second)-1]++;
}
for (i=0;i<n;i++) printf("%d\n",ans[i]);
return 0;
}