poj 2482 Stars in Your Window （线段树扫描线）

题目大意：

求一个窗体覆盖最多的星星的权值。

思路分析：

每个星星看成

左下点为x y

右上点为x+w-1 y+h-1 的矩形。

然后求出最大覆盖的和。

#include <cstdio>

#include <iostream>

#include <cstring>

#include <algorithm>

#define lson num<<1,s,mid

#define rson num<<1|1,mid+1,e

#define maxn 10005

using namespace std;

typedef long long LL;

LL res[maxn<<4];

LL sum[maxn<<4];

LL x[maxn<<4];

struct node

{

    LL s,e,h,type;

    bool operator < (const node &cmp)const

    {

        if(h==cmp.h)return type>cmp.type;

        return h<cmp.h;

    }

}scline[maxn<<1];

void pushup(int num)

{

    sum[num]=max(sum[num<<1],sum[num<<1|1]);

}

void pushdown(int num)

{

    if(res[num])

    {

        sum[num<<1]+=res[num];

        sum[num<<1|1]+=res[num];

        res[num<<1]+=res[num];

        res[num<<1|1]+=res[num];

        res[num]=0;

    }

}

void build(int num,int s,int e)

{

    res[num]=0;

    sum[num]=0;

    if(s==e)return;

    int mid=(s+e)>>1;

    build(lson);

    build(rson);

}

void update(int num,int s,int e,int l,int r,LL val)

{

    if(l<=s && r>=e)

    {

        res[num]+=val;

        sum[num]+=val;

        return;

    }

    int mid=(s+e)>>1;

    pushdown(num);

    if(l<=mid)update(lson,l,r,val);

    if(r>mid)update(rson,l,r,val);

    pushup(num);

}

int main()

{

    LL n,w,h;

    while(cin>>n>>w>>h)

    {

        for(int i=1;i<=n;i++)

        {

            LL ts,te,tt;

            cin>>ts>>te>>tt;

            scline[i*2-1].s=ts,scline[i*2-1].e=ts+w-1,scline[i*2-1].h=te,scline[i*2-1].type=tt;

            scline[i*2].s=ts,scline[i*2].e=ts+w-1,scline[i*2].h=te+h-1,scline[i*2].type=-tt;

            x[i*2-1]=ts,x[i*2]=ts+w-1;

        }

        sort(scline+1,scline+1+n*2);

        sort(x+1,x+1+n*2);

        int m=unique(x+1,x+1+n*2)-x;

        build(1,1,m);

        LL ans=0;

        for(int i=1;i<=n*2;i++)

        {

            int l=lower_bound(x+1,x+m,scline[i].s)-x;

            int r=lower_bound(x+1,x+m,scline[i].e)-x;

            update(1,1,m,l,r,scline[i].type);

            ans=max(ans,sum[1]);

        }

        cout<<ans<<endl;

    }

    return 0;

}

/*

2  1  5

0 0 100

0 4 101

*/