题目链接

题意:在一个二维平面上有n个星星,每个星星的等级为x,x为该星星左方和下方所包含的星星的数量(包含正左和正下的),输出每个等级各有多少星星,星星坐标按照y序递增给出,y值相同按照x递增给出。

题解:因为已经排好序了,我们每次更新加查询就可以了,因为后加入的一定是下方或者同行的,查询一下是不是左面的就行了。可以用线段树或者树状数组做,注意建树是N不是n,区间更新问题好像可以用什么lazy标记,这道题主要考察的还是思路。注意本题是按照值来进行查询的,建树的时候要用N建树。

#include <cstdio>
#include <cstring>
using namespace std;
#define m ((l+r)>>1)
#define lson rt<<1,l,m
#define rson rt<<1|1,m+1,r
#define N 32005
struct Tree
{
int l,r,sum;
}tree[N<<];
int ans[N<<];
//也可以不创建树
void build(int rt,int l,int r)
{
tree[rt].l=l;
tree[rt].r=r;
if(l==r) return;
build(lson);
build(rson);
}
void update(int rt,int l,int r,int data)
{
tree[rt].sum++;
if(l==r) return;
if(data<=m) update(lson,data);
else update(rson,data);
}
int query(int rt,int l,int r,int ll,int rr)
{
if(ll==l&&rr==r)
{
return tree[rt].sum;
}
if(rr<=m) return query(lson,ll,rr);
else if(ll>m) return query(rson,ll,rr);
else return query(lson,ll,m)+query(rson,m+,rr);
}
int main()
{
int x,y,n;
while(scanf("%d",&n)!=EOF)
{
build(,,n);
//puts("111");
memset(ans,,sizeof(ans));
for(int i=;i<n;i++)
{
scanf("%d%d",&x,&y);
x++;
//注意这里是N
ans[query(,,N,,x)]++;
update(,,N,x);
}
for(int i=;i<n;i++)
printf("%d\n",ans[i]);
}
return ;
}
05-08 14:56
查看更多