POJ 2352 Stars 线段树

题意：在一个二维平面上有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 ;

}

巴特西

POJ 2352 Stars 线段树

最新文章

热门文章