巢穴

about:blank

P2352

为树状树组量身打造的题...
不过我是线段树..

#include <iostream>
#include <stdio.h>
using namespace std;
const int MAXN=32005;
struct node
{
 int l,r;
 int d;
};
node t[MAXN*4];
int ans[MAXN];
void build(int l_,int r_,int p)
{
 t[p].l=l_;
 t[p].r=r_;
 t[p].d=0;
 if (l_!=r_)
 {
  build(l_,(l_+r_)/2,p<<1);
  build((l_+r_)/2+1,r_,(p<<1)+1);
 }
}

int find(int r_,int p)
{
    if (t[p].r<=r_) return t[p].d;
    int l=t[p].l;
    int r=t[p].r; 
    int sum=0;
    if (r_<=(l+r)/2) sum+=find(r_,p*2);
       else sum+=t[p*2].d+find(r_,p*2+1);
    return sum;
}
void insert(int x,int p)
{
    int l=t[p].l;
    int r=t[p].r;
    t[p].d++;
    if (l==r) return;
    if (x<=(l+r)/2) insert(x,p*2); else insert(x,p*2+1);  
}
int n;
int main()
{
    memset(ans,0,sizeof(ans));
    build(0,MAXN,1);
    cin>>n;
    for (int i=1;i<=n;i++)
    {
     int x,y;
     scanf("%d %d",&x,&y);
     ans[find(x,1)]++;
     insert(x,1);
    }
    for (int i=0;i<n;i++)
     cout<<ans[i]<<endl;
  //  system("pause");
    return 0;
}

posted on 2009-10-15 18:08 Vincent 阅读(160) 评论(0)  编辑 收藏 引用 所属分类: 数据结构与算法


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