Posted on 2011-11-02 20:21
C小加 閱讀(1517)
評論(0) 編輯 收藏 引用 所屬分類:
解題報告
我是用樹狀數(shù)組寫的。
注意到題上數(shù)據(jù)已經(jīng)排好序了，所以Y坐標(biāo)直接不用考慮。先找出x坐標(biāo)在i之前的點(diǎn)的數(shù)量r，則此點(diǎn)即為r級，然后更新此點(diǎn)。
#include <iostream>
#include <cstring>
using namespace std;
const int MAXN=15003;
const int MAXXY=32003;
int c[MAXXY],solve[MAXN];
void Init()
{
memset(solve,0,sizeof(solve));
memset(c,0,sizeof(c));
}
int Lowbit(int x)
{
return x&(-x);
}
void Update(int i)
{
while(i<=MAXXY)
{
c[i]+=1;
i+=Lowbit(i);
}
}
int Sum(int i)
{
int s=0;
while(i>0)
{
s+=c[i];
i-=Lowbit(i);
}
return s;
}
int main()
{
Init();
int n;
cin>>n;
int a,b,r;
for(int i=0;i<n;i++)
{
cin>>a>>b;
r=Sum(a+1);
solve[r]++;
Update(a+1);
}
for(int i=0;i<n;i++)
{
cout<<solve[i]<<endl;
}
return 0;
}