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

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

• Linux • 阅读 103

还是老规矩，传送门 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语言 刷题答案下载！

大家都在看

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