| Time Limit: 1000MS | Memory Limit: 65536KB | 64bit IO Format: %I64d & %I64u |
Description
Input
Output
Sample Input
5 1 1 5 1 7 1 3 3 5 5
Sample Output
1 2 1 1 0
刚开始以为用二维的树状数组求矩阵内元素和..然而只会一维的...然后学长提示了这题的y是递增的，也就是说star i+1肯定在star i的右边，因此只需判断是否在下方即可。于是题目变成了一维树状数组的前n项和，若star出现过此X坐标点标记为1即可。然后题目还有个坑点就是X可能是0，然而树状数组要从1开始。因此将题目中每个点均后移1个单位，答案不影响
代码：
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<sstream>
#include<cstring>
#include<cstdio>
#include<string>
#include<deque>
#include<cmath>
#include<queue>
#include<set>
#include<map>
using namespace std;
int tree[32010],n;
int pos[15010];
inline int lowbit(const int &k)
{
return k&-k;
}
inline void add(int k,const int &val)
{
while (k<=32009)
{
tree[k]+=val;
k+=lowbit(k);
}
return ;
}
inline int getsum(int k)
{
int sum=0;
while (k)
{
sum+=tree[k];
k-=lowbit(k);
}
return sum;
}
int main (void)
{
ios::sync_with_stdio(false);
int i,j,val,x,y;
while (cin>>n)
{
memset(pos,0,sizeof(pos));
memset(tree,0,sizeof(tree));
for (i=1; i<=n; i++)
{
cin>>x>>y;
pos[getsum(++x)]++;
add(x,1);
}
for (i=0; i<n; i++)
{
cout<<pos[i]<<endl;
}
}
return 0;
}
原文：http://www.cnblogs.com/Blackops/p/5399022.html