HUD 1541/BIT(数状数组)

题目链接

/*
按从左到右,从下到上的顺序给出星星的坐标,计算出level为[0,n)的星星的个数。
星星的level为该星星左下边(包括自己正下方的星星,但是不包括自己)星星的个数。
BIT模板题。
£:把星星的下标转化成从1开始。
£:想到用BIT做。
*/
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=35000+5;
const int ma=32000+5;
int c[maxn];
int lev[maxn];
int n;
inline int lowbit(int x)
{
return x&(-x);
}
int sum (int x)
{
int ret=0;
while(x>0)
{
ret+=c[x];
x-=lowbit(x);
}
return ret;
}
void add (int x,int d)
{
while(x<=ma)
{
c[x]+=d;
x+=lowbit(x);
}
}
int main ()
{
int n;
while(~scanf("%d",&n))
{
memset(c,0,sizeof(c));
memset(lev, 0, sizeof(lev));
int x,y;
for(int i=0;i<n;i++)
{
scanf("%d%d",&x,&y);
int Lev=sum(x+1);
lev[Lev]++;
add(x+1, 1);
}
for(int i=0;i<n;i++)
printf("%d\n",lev[i]);
}
return 0;
}
上一篇:android listview去掉分割线


下一篇:mysql中大数据表alter增加字段报错:"1034 Incorrect key file for table 'table_name'; try to repair it"