2352 Stars xiedi.rar(204 KB)

这道题我是用的线段树的特例，点数来完成的，算法可以看附件中，谢迪大牛的PPT。

源代码：

#include <iostream>
using namespace std;
typedef struct Node
{
 int l,r;
 int count;
}node;
class PointTree                                              //点数类
{
    private:
  node p[1<<18];
 public:
  void init_tree(int l,int r,int index)            //初始化
  {
    p[index].l=l;
    p[index].r=r;
    p[index].count=0;
   if(l==r)
     return ;
   else
   {
    int mid=(l+r)/2;
    init_tree(l,mid,2*index);
    init_tree(mid+1,r,2*index+1);
   }
  }
  void insert(int x,int index)                            //插入点
  {
   p[index].count++;
   if(p[index].r==x&&p[index].l==x)
    return ;
   else
   {
    int mid=(p[index].r+p[index].l)/2;
    if(x<=mid)
     insert(x,2*index);
    else
     insert(x,2*index+1);
   }
  }
  int level(int l,int r,int index)                          //大小
  {
   if(p[index].l==l&&p[index].r==r)
    return p[index].count;
   else
   {
    int mid=(p[index].r+p[index].l)/2;
    if((mid+1)<=l)
     return level(l,r,2*index+1);
    else if(r<=mid)
     return level(l,r,2*index);
    else
     return level(l,mid,2*index)+level(mid+1,r,2*index+1);
   }
  }
};
int s[15002];
PointTree t;
int main()
{
 t.init_tree(0,32000,1);
 memset(s,0,sizeof(s));
 int n;
 cin >>n;
 for(int i=0;i<n;i++)
 {
  int x,y;
  cin >>x>>y;
  t.insert(x,1);
  s[t.level(0,x,1)]++;
 }
 for(int j=1;j<=n;j++)
 {
  cout<<s[j]<<endl;
 }
 return 0;
}