思路:
这道题因为是按照y坐标增序给出的,所以前面给出的星星,一定在后面的星星的 "下方”, 对于某个星星就判断前面的星星有多少个的x坐标小于等于这个星星,就能判断这个星星是多少级的
AC代码:
最近在学线段树,给出线段树做法的代码
#include<iostream>
const int N = 1e5+9;
int ans[N];
using namespace std;
struct node
{
int l,r;
int sum;
}tr[N*4];
void pushup(int u)
{
tr[u].sum = tr[u<<1].sum + tr[u<<1|1].sum;
}
void build(int u,int l,int r)
{
if(l==r) tr[u] = {
l,r,0};
else
{
int mid = l+r >>1;
tr[u] ={
l,r,0};
build(u<<1,l,mid);
build(u<<1|1,mid+1,r);
//pushup(u);
}
}
void modify(int u,int x,int v)
{
if(tr[u].l==tr[u].r) tr[u].sum+=v;
else
{
int mid = tr[u].l + tr[u].r >>1;
if(x<=mid) modify(u<<1,x,v);
else modify(u<<1|1,x,v);
pushup(u);
}
}
int query(int u,int l,int r)
{
if(tr[u].l>=l&&tr[u].r<=r) return tr[u].sum;
int mid = tr[u].l + tr[u].r>>1;
int sum = 0;
//注意这里l,r不变
if(l<=mid) sum+=query(u<<1,l,r);
if(r>mid) sum+= query(u<<1|1,l,r);
return sum;
}
int main()
{
int n;
scanf("%d",&n);
//注意这里初始化范围要大于32000
build(1,1,32009);
for(int i=0;i<n;i++)
{
int x,y;
scanf("%d%d",&x,&y);
x++;
ans[query(1,1,x)]++;
modify(1,x,1);
}
for(int i=0;i<n;i++) printf("%d\n",ans[i]);
return 0;
}