459
poj 2352 Stars 树状数组
统计x之前出现数字的次数，线段树和树状数组都可以，但明显树状数组更简洁
/*
author:jxy
lang:C/C++
university:China,Xidian University
**If you need to reprint,please indicate the source**
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <queue>
#define INF 1E9
using namespace std;
int ans[15005];
int c[32005],n;
inline int low(int x)
{
return x&-x;
}
int add(int pos,int num)
{
while(pos<=32001)
{
c[pos]+=num;
pos+=low(pos);
}
}
int query(int pos)
{
int ans=0;
while(pos>0)
{
ans+=c[pos];
pos-=low(pos);
}
return ans;
}
int main()
{
memset(ans,0,sizeof(ans));
memset(c,0,sizeof(c));
scanf("%d",&n);
int i,x,y,t;
for(i=0;i<n;i++)
{
scanf("%d%d",&x,&y);
x++;
ans[query(x)]++;
add(x,1);
}
for(i=0;i<n;i++)
printf("%d\n",ans[i]);
}
最后更新：2017-04-03 16:48:46