SGU 319 Kalevich Strikes Back(线段树扫描线)

SGU 319 Kalevich Strikes Back(线段树扫描线)

大家好,又见面了,我是全栈君,祝每个程序员都可以多学几门语言。

题目大意:

n个矩形,将一个大矩形分成 n+1 块。矩形之间不重合,可是包括。求这n+1个矩形的面积

思路分析:

用线段树记录他们之间的父子关系。然后dfs 计算面积。

当给出的矩形上边的时候,就要记录到该矩形的父亲去。

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#define lson num<<1,s,mid
#define rson num<<1|1,mid+1,e
#define maxn 70010

using namespace std;
typedef long long LL;

int cov[maxn<<2];
LL area[maxn<<1];
int W,H;

struct node
{
    int s,e,h,type;
    bool operator < (const node &cmp)const
    {
        return h<cmp.h;
    }
}scline[maxn<<1];

struct foo
{
    int s,e,h;
}sqr[maxn<<2];

int x[maxn<<1];
int pre[maxn<<1];

void pushdown(int num)
{
    if(cov[num]!=-1){
        cov[num<<1]=cov[num<<1|1]=cov[num];
        cov[num]=-1;
    }
}
void build(int num,int s,int e)
{
    cov[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,int val)
{
    if(l<=s && r>=e)
    {
        if(val<0)cov[num]=pre[abs(val)];
        else cov[num]=val;
        return;
    }
    pushdown(num);
    int mid=(s+e)>>1;
    if(l<=mid)update(lson,l,r,val);
    if(r>mid)update(rson,l,r,val);
}

int PRE;
int query(int num,int s,int e,int l,int r)
{


    if(cov[num]!=-1)
    {
        return cov[num];
    }
    pushdown(num);
    int mid=(s+e)>>1;
    if(r<=mid)return query(lson,l,r);
    else if(l>mid)return query(rson,l,r);
    else return query(lson,l,mid);
}

int head[maxn<<1];
int next[maxn<<1];
int to[maxn<<1];
int tot;
void add(int a,int b)
{
    next[tot]=head[a];
    head[a]=tot;
    to[tot]=b;
    tot++;
}
LL getarea(int index)
{
    return (LL)sqr[index].h*(LL)(sqr[index].e-sqr[index].s);
}
void dfs(int x)
{
    for(int s=head[x];s!=0;s=next[s])
    {
        area[x]-=getarea(to[s]);
        dfs(to[s]);
    }
}

int main()
{
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        tot=1;

        memset(pre,0,sizeof pre);

        scanf("%d%d",&W,&H);
        area[0]=(LL)W*(LL)H;
        sqr[0].s=0;sqr[0].e=W;sqr[0].h=H;
        for(int i=1;i<=n;i++)
        {
            int x1,y1,x2,y2;
            scanf("%d%d%d%d",&x1,&y1,&x2,&y2);

            if(x1>x2)swap(x1,x2);
            if(y1>y2)swap(y1,y2);
            sqr[i].s=x1;sqr[i].e=x2;sqr[i].h=y2-y1;

            scline[2*i-1].s=x1;
            scline[2*i-1].e=x2;
            scline[2*i-1].h=y1;
            scline[2*i-1].type=i;
            x[2*i-1]=x1;

            scline[2*i].s=x1;
            scline[2*i].e=x2;
            scline[2*i].h=y2;
            scline[2*i].type=-i;
            x[2*i]=x2;
        }

        x[2*n+1]=0;
        x[2*n+2]=W;

        for(int i=1;i<=n;i++)
        area[i]=getarea(i);

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

        build(1,0,m);

        sort(scline+1,scline+2*n+1);
        memset(head,0,sizeof head);
        tot=1;
        for(int i=1;i<=2*n;i++)
        {
            int l=lower_bound(x+1,x+m+1,scline[i].s)-(x+1);
            int r=lower_bound(x+1,x+m+1,scline[i].e)-(x+1);


            if(scline[i].type>0)
            {
                pre[scline[i].type]=query(1,0,m,l,r);
                printf("%d %d\n",scline[i].type,pre[scline[i].type]);
                add(pre[scline[i].type],scline[i].type);
               
            }
            update(1,0,m,l,r,scline[i].type);
        }

        dfs(0);
        sort(area,area+n+1);

        for(int i=0;i<=n;i++)
        printf("%lld%c",area[i],i==n?'\n':' ');
    }
    return 0;
}
/*
2
5 5
1 1 4 4
2 2 3 3

4
10 10
1 1 5 5
2 2 3 4
6 1 9 9
7 2 8 3

4
10 10
1 1 9 6
2 2 5 5
2 7 8 9
3 6 5 7
*/

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/118539.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • 5线上模式刷2亿bug_GTA5还想冲销量?玩家利用BUG刷钱,遭受比封号更严厉惩罚

    5线上模式刷2亿bug_GTA5还想冲销量?玩家利用BUG刷钱,遭受比封号更严厉惩罚  《GTA5》作为一款神级开放世界游戏,即便已经发售了七年,凭借其优秀的品质以及耐玩性,而今仍旧是许多玩家讨论的焦点。不过在近期,鲜有出现负面消息的R星却因为线上模式的BUG而受到了玩家们的非议。  《GTA5》说是游戏,但你在玩的过程中不自觉就代入到了主角的视角中。跟现实世界一样,美金在游戏中也非常重要。有了钱,你就可以在洛圣都这个虚拟世界中过自己想要的生活。  但玩家在游戏中无论是使用合法的…

  • 高级面试题–SpringBoot启动流程解析「建议收藏」

    高级面试题–SpringBoot启动流程解析「建议收藏」写在前面:由于该系统是底层系统,以微服务形式对外暴露dubbo服务,所以本流程中SpringBoot不基于jetty或者tomcat等容器启动方式发布服务,而是以执行程序方式启动来发布(参考下图keepRunning方法)。本文以调试一个实际的SpringBoot启动程序为例,参考流程中主要类类图,来分析其启动逻辑和自动化配置原理。总览:上图为SpringBoot启动结构图,我们发现启动流程…

  • file_get_contents(“php://input”)[通俗易懂]

    file_get_contents(“php://input”)

  • ElasticSearch 简单的 搜索 聚合 分析

    ElasticSearch 简单的 搜索 聚合 分析一、搜索1.DSL搜索全部数据没有任何条件查询名称包含xxx的商品,同时按照价格降序排序分页查询商品from第几条开始size获取几条查询结果中返回的字段设置2、query

  • C++\QT常见面试题[通俗易懂]

    C++\QT常见面试题[通俗易懂]1.C与C++的区别2.深拷贝和浅拷贝的区别3.指针和引用的区别4.什么是面向对象,面向对象的三大特征是什么?5.static关键字的用法6.const关键字的用法7.什么是函数重载8.创建的对象有几种方式,有什么区别9.什么是构造函数10.什么是this指针11.抽象类是什么12.什么是封装、继承、多态13.私有继承,保护继承和公有继承的区别14.友元函数15.new和delete16.C++STL容器有哪些17.什么是面向对象编程的开放封闭原则?18.内联函数与宏的区

  • 大疆测评攻略

    他说大疆测评也刷人比例还很高总结来网上的有关注意事项都是各方面搬一点,总结一下测评的题主要为:性格测试,逻辑测试,计算题,场景题。这类的题⽬我能给你们的建议只是针对性格测试和场景题这类的主观性题。DJI大疆2019在线测评-知乎https://zhuanlan.zhihu.com/p/76053124大疆招聘网申测评测试笔试题https://zhuanlan.zhihu.com/p/157371591大疆在线测试三段论https://bbs.yingjiesheng.com/thr

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号