描述
永恒和mx正在玩一个即时战略游戏，名字嘛~~~~~~恕本人记性不好，忘了-_-b。
mx在他的基地附近建立了n个战壕，每个战壕都是一个独立的作战单位，射程可以达到无限（“mx不赢定了？！？”永恒ftING…@_@）。
但是，战壕有一个弱点，就是只能攻击它的左下方，说白了就是横纵坐标都不大于它的点（mx：“我的战壕为什么这么菜”ToT）。这样，永恒就可以从别的地方进攻摧毁战壕，从而消灭mx的部队。
战壕都有一个保护范围，同它的攻击范围一样，它可以保护处在它左下方的战壕。所有处于它保护范围的战壕都叫做它的保护对象。这样，永恒就必须找到mx的战壕中保护对象最多的点，从而优先消灭它。
现在，由于永恒没有时间来计算，所以拜托你来完成这个任务：
给出这n个战壕的坐标xi、yi，要你求出保护对象个数为0，1，2……n-1的战壕的个数。
输入格式
第一行，一个正整数n（1<=n<=15000）
接下来n行，每行两个数xi,yi，代表第i个点的坐标
（1<=xi,yi<=32000）
注意：可能包含多重战壕的情况（即有数个点在同一坐标）
输出格式
输出n行，分别代表保护对象为0，1，2……n-1的战壕的个数。
样例输入
5
1 1
5 1
7 1
3 3
5 5
样例输出
1
2
1
1
0
代码
#include <cstdio>
#include <cmath>
#include <cstring>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
#include <sstream>
#include <queue>
#include <typeinfo>
#include <fstream>
#include <map>
#include <stack>
typedef long long ll;
using namespace std;
//freopen("D.in","r",stdin);
//freopen("D.out","w",stdout);
#define sspeed ios_base::sync_with_stdio(0);cin.tie(0)
#define test freopen("test.txt","r",stdin)
#define maxn 200101
#define mod 1000000009
#define eps 1e-9
const int inf=0x3f3f3f3f;
const ll infll = 0x3f3f3f3f3f3f3f3fLL;
inline ll read()
{
ll x=,f=;
char ch=getchar();
while(ch<''||ch>'')
{
if(ch=='-')f=-;
ch=getchar();
}
while(ch>=''&&ch<='')
{
x=x*+ch-'';
ch=getchar();
}
return x*f;
}
//************************************************************************************** struct ss
{
int r,l,v;
}tr[*];
struct data
{
int x,y;
}a[];
bool cmp(data a,data b){return (a.x==b.x)?(a.y<b.y):(a.x<b.x);}
int ans[],n;
void build(int k,int l,int r)
{
tr[k].l=l;
tr[k].r=r;
tr[k].v=;
if(l==r) return ;
int mid=(l+r)>>;
build(k<<,l,mid);
build(k<<|,mid+,r);
}
void insert(int k,int ls,int rs)
{
int mid=(tr[k].l+tr[k].r)>>;
if(tr[k].l==ls&&tr[k].r==rs)
{
tr[k].v++;
return ;
}
else if(tr[k].l==tr[k].r)return ;
else if(rs<=mid){
insert(k<<,ls,rs);
}
else if(ls>mid)
{
insert(k<<|,ls,rs);
}
else {
insert(k<<,ls,mid);
insert(k<<|,mid+,rs);
}
}
int ask(int k,int x)
{
if(tr[k].l==tr[k].r) return tr[k].v;
int mid=(tr[k].l+tr[k].r)>>;
if(x<=mid)return tr[k].v+(ask(k<<,x));
else return tr[k].v+(ask(k<<|,x));
}
int main()
{ scanf("%d",&n);
build(,,);
for(int i=;i<=n;i++)
{
scanf("%d%d",&a[i].x,&a[i].y);
}
sort(a+,a+n+,cmp);
for(int i=;i<=n;i++)
{
ans[ask(,a[i].y)]++;
insert(,a[i].y,);
}
for(int i=;i<n;i++)
{
printf("%d\n",ans[i]);
}
return ;
}