#include<stdio.h>
#define SIZE1 32000
#define SIZE2 15000
int c[SIZE1],a[SIZE1],out[SIZE2],n;
int lowbit(int k)
{
return k&(-k);
}
int sum(int k)
{
int ret=0;
while(k>0)
{
ret+=c[k];
k-=lowbit(k);
}
return ret;
}
void change(int pos,int delt)
{
while(pos<=SIZE1)
{
c[pos]+=delt;
pos+=lowbit(pos);
}
}
void init()
{
int i;
int x,y;
for(i=0;i<n;i++)
{
scanf("%d%d",&x,&y);
x++;
out[sum(x-1)+a[x]]++;
change(x,1);
a[x]++;
}
}
int main()
{
int i;
scanf("%d",&n);
init();
for(i=0;i<n;i++)
printf("%d\n",out[i]);
}
pip來了，但是他說他也不會他是線段樹過的。。。。。
線段樹。。。。。代碼不是我的。。。網(wǎng)上的。。。。不過不錯。。。題目有個條件就是按y升序給出數(shù)據(jù)。。。。所以可以用樹狀數(shù)組，其實可以排序在用的。。。。。繼續(xù)物理。。。。關(guān)機。。。  回復(fù)  更多評論