1. Johngo学长首页
  2. 技术点详细复盘专题
  3. Linux

线段树扫描线（二）矩形周长 以hdu1828为例

• Linux • 阅读 86

还是老规矩，传送门 hdu 1828

依然不做过多解释，给出n个矩形，求这些矩形组合而成的图形的周长（中间镂空的部分也算）

还是像扫面线（一）一样，自下而上扫描，

我们先只考虑横线，发现只要每次加上被覆盖的区间长度的变化值的绝对值就能统计出横向的答案，

但竖线怎么办？

有一种朴素的办法，自下而上扫过一次后，从左到右在扫一遍，常数问题（好像不卡）

接下来，讲一种更好的办法。

我所说的办法，就是在自下而上扫描时，同时统计出竖线的长度和。

每条竖线的长度很好统计，用这一条扫描线的高度减去上一条扫描线的的高度即可，但有多少条竖线呢？

我们可以在线段树中添加三个成员，这样总共就会有五个：

struct node
{
      int dis;  //被覆盖的长度
      int cnt;  //被整体覆盖了几次
      int ls;   //左端点是否被覆盖
      int rs;   //右端点是否被覆盖
      int num;  //区间中总共有多少条竖线
};

接下来，考虑pushup()要怎么写

更新dis的部分在此不再赘述，详见最下面代码或者扫描线（一）

正确的更新竖线的代码是这样的

tre[nc].ls=tre[2*nc].ls;
tre[nc].rs=tre[2*nc+1].rs;
tre[nc].num=tre[2*nc].num+tre[2*nc+1].num;
if(tre[2*nc].rs&&tre[2*nc+1].ls)
{
    tre[nc].num-=2;
}

关键点在if里边，画张图

线段树扫描线（二）矩形周长 以hdu1828为例

如图所示，L到R的的两个子区间中，有两条竖线在和并之后消失了，其原因是这两条线段刚好覆盖了分点，因而，要加上if来保证其正确性

然后就是一个小细节，重边要先加后减，否则就会多统计重边，排序时在cmp中处理一下即可。

奉上代码

  1 #include
  2 #include
  3 #include
  4 #include
  5 using namespace std;
  6 map<int,int> mp;
  7 int ls[20100],x1,x2,y1,y2;
  8 int n,cnt,cd;
  9 struct edge
 10 {
 11     int l,r,val,h;
 12 }eds[10100];
 13 struct node
 14 {
 15     int cov,dis,ls,rs,num;
 16 }tre[80100];
 17 int cmp(edge a,edge b)
 18 {
 19     if(a.h==b.h)
 20     {
 21         return a.val>b.val;
 22     }
 23     return a.h<b.h;
 24 }
 25 int fabs(int a){return a>0?a:-a;}
 26 void init()
 27 {
 28     cnt=1;
 29     cd=1;
 30     mp.clear();
 31     memset(ls,0,sizeof(ls));
 32 }
 33 int fd(int tar)
 34 {
 35     int l=1,r=cd;
 36     while(l<r)
 37     {
 38         int mid=(l+r)/2;
 39         if(ls[mid]<tar)
 40         {
 41             l=mid+1;
 42         }
 43         else
 44         {
 45             r=mid;
 46         }
 47     }
 48     return l;
 49 }
 50 void pushup(int L,int R,int nc)
 51 {
 52     if(tre[nc].cov)
 53     {
 54         tre[nc].dis=ls[R+1]-ls[L];
 55         tre[nc].num=2;
 56     }
 57     else
 58     {
 59         if(L==R)
 60         {
 61             tre[nc].dis=0;
 62             tre[nc].ls=0;
 63             tre[nc].rs=0;
 64             tre[nc].num=0;
 65         }
 66         else
 67         {
 68             tre[nc].dis=tre[2*nc].dis+tre[2*nc+1].dis;
 69             tre[nc].num=tre[2*nc].num+tre[2*nc+1].num;
 70             if(tre[2*nc].rs&&tre[2*nc+1].ls)
 71             {
 72                 tre[nc].num-=2;
 73             }
 74             tre[nc].ls=tre[2*nc].ls;
 75             tre[nc].rs=tre[2*nc+1].rs;
 76         }
 77     }
 78 }
 79 void ins(int l,int r,int dt,int nc,int L,int R)
 80 {
 81     if(l=R)
 82     {
 83         tre[nc].cov+=dt;
 84         tre[nc].ls+=dt;
 85         tre[nc].rs+=dt;
 86         if(tre[nc].cov)
 87         {
 88             tre[nc].dis=ls[R+1]-ls[L];
 89             tre[nc].num=2;
 90         }
 91         else
 92         {
 93             if(L==R)
 94             {
 95                 tre[nc].dis=0;
 96                 tre[nc].ls=0;
 97                 tre[nc].rs=0;
 98                 tre[nc].num=0;
 99             }
100             else
101             {
102                 tre[nc].num=tre[2*nc].num+tre[2*nc+1].num;
103                 if(tre[2*nc].rs&&tre[2*nc+1].ls)
104                 {
105                     tre[nc].num-=2;
106                 }
107                 tre[nc].ls=tre[2*nc].ls;
108                 tre[nc].rs=tre[2*nc+1].rs;
109                 tre[nc].dis=tre[2*nc].dis+tre[2*nc+1].dis;
110             }
111         }
112         return;
113     }
114     int mid=(L+R)/2;
115     if(lmid)
116     {
117         ins(l,r,dt,2*nc,L,mid);
118     }
119     if(r>mid)
120     {
121         ins(l,r,dt,2*nc+1,mid+1,R);
122     }
123     pushup(L,R,nc);
124 }
125 int main()
126 {
127     while(scanf("%d",&n)!=EOF)
128     {
129         init();
130         for(int i=1;i)
131         {
132             scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
133             eds[cnt].h=y1;
134             eds[cnt].l=x1;
135             eds[cnt].r=x2;
136             eds[cnt].val=1;
137             cnt++;
138             eds[cnt].h=y2;
139             eds[cnt].l=x1;
140             eds[cnt].r=x2;
141             eds[cnt].val=-1;
142             cnt++;
143             if(!mp[x1])
144             {
145                 mp[x1]=1;
146                 ls[cd]=x1;
147                 cd++;
148             }
149             if(!mp[x2])
150             {
151                 mp[x2]=1;
152                 ls[cd]=x2;
153                 cd++;
154             }
155         }
156         sort(ls+1,ls+cd);
157         for(int i=1;i)
158         {
159             eds[i].l=fd(eds[i].l);
160             eds[i].r=fd(eds[i].r);
161         }
162         sort(eds+1,eds+cnt,cmp);
163         ins(eds[1].l,eds[1].r-1,eds[1].val,1,1,cd-1);
164         int last=eds[1].h,ans=tre[1].dis,lasa=ans;
165         for(int i=2;i)
166         {
167             int n0=tre[1].num;
168             ins(eds[i].l,eds[i].r-1,eds[i].val,1,1,cd-1);
169             ans+=fabs(tre[1].dis-lasa);
170             ans+=(eds[i].h-last)*n0;
171             lasa=tre[1].dis;
172             last=eds[i].h;
173         }
174         printf("%d\n",ans);
175     }
176 };i++;i++

大家可能会发现这和（一）中的代码神似，没错，鄙人就是根据（一）中的代码加以修改的！！！！！！！！！！！！！！！

Original: https://www.cnblogs.com/Grharris/p/10392495.html
Author: Grharris
Title: 线段树扫描线（二）矩形周长 以hdu1828为例

原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/578004/

转载文章受原作者版权保护。转载请注明原作者出处！

赞 (0)
0

【自取】最近整理的，有需要可以领取学习：



Linux核心资料大放送~

全栈面试题汇总（持续更新&可下载）

一个提高学习100%效率的工具！

【超详细】深度学习面试题目！

LeetCode Python刷题答案下载！

LeetCode Java版刷题答案下载！

LeetCode C++ 版本，抓紧保存！

LeetCode GO语言 刷题答案下载！

大家都在看

  • 【Docker搭建】0. 在CentOS下安装/卸载Docker

    警告：切勿在没有配置 Docker YUM 源的情况下直接使用 yum 命令安装 Docker. 系统要求Docker CE 支持 64 位版本 CentOS 7，并且要求内核版本…

    Linux 2023年6月13日
    069

  • 红警快捷键图示

    最近，实验室的同学们 周末偶尔会玩一玩红警，回忆一下童年，挺愉快的。下面记录一下快捷键，方便操作； 看到B站上红警08，还有对应的快捷键教学视频，也可以直接学习一下； https:…

    Linux 2023年6月14日
    0105

  • MySQL之视图、触发器、事务、索引及其他知识补充

    一、视图 视图是将SQL语句的查询结果当做虚拟表实体化保存起来，以后可以反复使用 create view teacher2course as select * from teach…

    Linux 2023年6月14日
    082

  • jmeter beanshell 从文件中获取随机参数

    loadruner 参数化有个功能，可以设置在脚本每次出现参数时，自动更换参数值。在做jmeter自动化测试过程中，同一个请求中出现多个参数值，如一个接口可以添加n个信息的请求 […

    Linux 2023年5月28日
    0203

  • HTS恢复检查脚本

    #!/bin/bash #program:HTS-A数据库和插件检查 #author:sundz #version 20220531 v1 创建脚本 生成sql的表和字段汇总;ab…

    Linux 2023年6月7日
    083

  • go redis锁

    redis经常用作分布式锁，这里记录一个简单的锁代码如下： package main import ( "crypto/rand" "encoding…

    Linux 2023年5月28日
    0110

  • 标签泄露 Label leaking

    404. 抱歉，您访问的资源不存在。 可能是网址有误，或者对应的内容被删除，或者处于私有状态。 代码改变世界，联系邮箱 contact@cnblogs.com 园子的商业化努力-困…

    Linux 2023年6月7日
    082

  • 剑指offer计划链表

    剑指offer计划链表 从尾到头打印链表 /** * public class ListNode { * int val; * ListNode next = null; * * …

    Linux 2023年6月11日
    065

  • django_响应对象

    Django_响应对象 响应对象 响应对象有三种形式：HttpResponse()render()Redirect() （1） HttpResponse（） django服务器接收…

    Linux 2023年6月7日
    098

  • TCP三次握手与四次挥手

    什么是三次握手？ 一般情况下，连接是由客户端向服务端发起的。 第一次，客户端发送一个TCP数据报并将SYN同步位置为1，表示要建立连接，此时客户端会从CLOSED状态变为SYN_S…

    Linux 2023年6月8日
    095

  • make及makefile简单介绍

    GUN make是一种代码维护工具。 make工具会根据makefile文件定义的规则和步骤，完成整个软件项目的代码维护工作。 一般用来简化编译工作，可以极大地提高软件开发地效率。…

    Linux 2023年6月7日
    059

  • 每天一个 HTTP 状态码 前言

    HTTP 状态码由 3 位阿拉伯数字构成，其中第一位用于定义 HTTP 响应的类型… 前前言 在重新开始写博文（其实大多也就最多算是日常笔记小结）之际，就想着从短小精悍…

    Linux 2023年6月7日
    087

  • 用 shell 脚本制造连接频繁中断的场景

    问题的提出 最近在准备客户端的新版本，在内部灰度过程中，发现一类奇怪的 dump，通过查看日志和堆栈，可以确定是因为每次连上后台就被后台断开了、导致多次重连后随机发生的崩溃。dum…

    Linux 2023年6月6日
    081

  • SpringBoot-swagger

    SpringBoot整合swagger SpringBoot-swagger 13.1 导入相关依赖 io.springfox springfox-swagger-ui 2.9.2…

    Linux 2023年6月14日
    082

  • JuiceFS v1.0 正式发布，首个面向生产环境的 LTS 版本

    今天，JuiceFS v1.0 发布了 🎉 经过了 18 个月的持续迭代和大量生产环境的广泛验证，此版本将成为第一个被长期维护的稳定版（LTS）。同时，该版本提供完整的向前兼容，所…

    Linux 2023年6月14日
    088

  • TCP三次握手 四次挥手

    最近在恶补计算机网络方面的知识，之前对于TCP的三次握手和四次分手也是模模糊糊，对于其中的细节更是浑然不知，最近看了很多这方面的知识，也在系统的学习计算机网络，加深自己的CS功底，…

    Linux 2023年6月7日
    077
亲爱的 Coder【最近整理，可免费获取】👉 最新必读书单  | 👏 面试题下载  | 🌎 免费的AI知识星球