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

2020-12-13 05:07

阅读：549

标签：os io for re c line

题目大意：

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

思路分析：

每一个星星看成

左下点为x y

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

然后求出最大覆盖的和。

#include 
#include 
#include 
#include 
#define lson numcmp.type;
        return h>1;
    build(lson);
    build(rson);
}
void update(int num,int s,int e,int l,int r,LL val)
{
    if(l=e)
    {
        res[num]+=val;
        sum[num]+=val;
        return;
    }
    int mid=(s+e)>>1;
    pushdown(num);
    if(lmid)update(rson,l,r,val);
    pushup(num);
}
int main()
{
    LL n,w,h;
    while(cin>>n>>w>>h)
    {
        for(int i=1;i>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

poj 2482 Stars in Your Window （线段树扫描线）,搜素材,soscw.com
poj 2482 Stars in Your Window （线段树扫描线）
标签：os   io   for   re   c   line   
原文地址：http://blog.csdn.net/u010709592/article/details/37989157

上一篇：andriod 在windows上环境配置

下一篇：秒懂Hash算法（一）：什么是Hash

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：poj 2482 Stars in Your Window （线段树扫描线）
文章链接：http://soscw.com/essay/30447.html

亲，登录后才可以留言！

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

评论

热门文章

推荐文章

最新文章

置顶文章