POJ 2352 Stars（线段树）

题目地址：

今天的周赛被虐了。

。

TAT..线段树太渣了。。得好好补补了（尽管是从昨天才開始学的。。不能算补。。。）

这题还是非常easy的。。维护信息是每个横坐标的出现的次数。

代码例如以下：

#include <iostream>

#include <cstdio>

#include <string>

#include <cstring>

#include <stdlib.h>

#include <math.h>

#include <ctype.h>

#include <queue>

#include <map>

#include <set>

#include <algorithm>

using namespace std;

#define lson l, mid, rt<<1

#define rson mid+1, r, rt<<1|1

struct node

{

    int x, y;

} star[40000];

int cmp(node x, node y)

{

    if(x.y==y.y)

    {

        return x.x<y.x;

    }

    return x.y<y.y;

}

int sum[323000], _hash[130000];

void PushUp(int rt)

{

    sum[rt]=sum[rt<<1]+sum[rt<<1|1];

}

void update(int x, int l ,int r, int rt)

{

    if(l==r)

    {

        sum[rt]++;

        return ;

    }

    int mid=l+r>>1;

    if(x<=mid) update(x,lson);

    else update(x,rson);

    PushUp(rt);

}

int query(int ll, int rr, int l, int r, int rt)

{

    if(ll<=l&&rr>=r)

    {

        return sum[rt];

    }

    int mid=l+r>>1;

    int ans=0;

    if(ll<=mid) ans+=query(ll,rr,lson);

    if(rr>mid) ans+=query(ll,rr,rson);

    return ans;

}

int main()

{

    int n, x, y, i, j, ans, max1=-1;

    scanf("%d",&n);

    memset(sum,0,sizeof(sum));

    for(i=0; i<n; i++)

    {

        scanf("%d%d",&star[i].x,&star[i].y);

        if(max1<star[i].x)

            max1=star[i].x;

    }

    sort(star,star+n,cmp);

    memset(_hash,0,sizeof(_hash));

    for(i=0; i<n; i++)

    {

        ans=query(0,star[i].x,0,max1,1);

        update(star[i].x,0,max1,1);

        _hash[ans]++;

    }

    for(i=0; i<n; i++)

    {

        printf("%d\n",_hash[i]);

    }

    return 0;

}