巢穴

about:blank

P2352

这次是用树状数组过的..

#include <iostream>
using namespace std;

const int MAXN=15001;
int N;
int ANS[MAXN*2];
int max_=32005;
int c[65000];
inline int lowbit(int x)
{
    return x&(x^(x-1));
}
int find(int x)
{
    int count_=0;
    while(x>0)
    {
     count_+=c[x];
     x=x-lowbit(x);
    }
    return count_;
}
void insert(int x)
{
     while(x<=max_)
     {
      c[x]++;
      x=x+lowbit(x);
     }
}
int main()
{
    memset(ANS,0,sizeof(ANS));
    cin>>N;
    for (int i=1;i<=N;i++)
    {
     int a,b;
     cin>>a>>b;
     a++;
     ANS[find(a)]++;
     insert(a);
    }
    for (int i=0;i<=N-1;i++)
     cout<<ANS[i]<<endl;
    system("pause");
    return 0;
}

posted on 2009-11-11 21:30 Vincent 阅读(115) 评论(0)  编辑 收藏 引用 所属分类: 数据结构与算法


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理