正文

poj3277cityhorizon

author  author  2022-08-01  740

关键词：

City Horizon

Time Limit: 2000MS		Memory Limit: 65536K
Total Submissions: 18555		Accepted: 5114

Description

Farmer John has taken his cows on a trip to the city! As the sun sets, the cows gaze at the city horizon and observe the beautiful silhouettes formed by the rectangular buildings.

The entire horizon is represented by a number line with N (1 ≤ N ≤ 40,000) buildings. Building i‘s silhouette has a base that spans locations A_i through B_i along the horizon (1 ≤ A_i < B_i ≤ 1,000,000,000) and has height H_i(1 ≤ H_i ≤ 1,000,000,000). Determine the area, in square units, of the aggregate silhouette formed by all N buildings.

Input

Line 1: A single integer: N
Lines 2..N+1: Input line i+1 describes building i with three space-separated integers: A_i, B_i, and H_i

Output

Line 1: The total area, in square units, of the silhouettes formed by all N buildings

Sample Input

Sample Output

Hint

The first building overlaps with the fourth building for an area of 1 square unit, so the total area is just 3*1 + 1*4 + 2*2 + 2*3 - 1 = 16.

题目大意：在水平直线上给定一组矩形，这些矩形的底边在同一水平线上，求这些矩形占据的面积。

题目分析：很显然，这些矩形的长和高都不一样，还会有重合的区域。如何求这些矩形的面积呢？画个图就知道了。

本题需要注意：

离散化的手法；

延迟更新的手法：在最后求面积时延迟

long long （强制转换）；

 1 #include <iostream>
 2 #include <algorithm>
 3 #include <cstdio>
 4 #include <cstring>
 5 using namespace std;
 6 
 7 #define lson l,m,rt<<1
 8 #define rson m,r,rt<<1|1
 9 
10 typedef long long LL;
11 
12 const int maxn=40005;
13 const int maxl=maxn*2;
14 int a[maxn],b[maxn],c[maxn];
15 int jh[maxl];
16 int h[maxl<<2],tag[maxl<<2];
17 int N,M;
18 
19 void UpDate(int L,int R,int d,int l,int r,int rt)
20 {
21     if(L<=l&&r<=R)
22     {
23         if(h[rt]<d) h[rt]=d;
24         return;
25     }
26     if(l+1==r) return;
27     int m=(l+r)>>1;
28     if(L<=m) UpDate(L,R,d,lson);
29     if(R>=m) UpDate(L,R,d,rson);
30 }
31     
32 LL Query(int l,int r,int rt,int height)//lazy lazy lazy
33 {
34     if(height>h[rt]) h[rt]=height;
35     if(l+1==r) return (LL)(jh[r]-jh[l])*h[rt];
36     int m=(l+r)>>1;
37     LL a=Query(lson,h[rt]);
38     LL b=Query(rson,h[rt]);
39     return a+b;
40 }
41 
42 int bfind(int x)
43 {
44     int l,r;
45     l=0,r=M+1;
46     while(l<r)
47     {
48         int m=(l+r)>>1;
49         if(jh[m]==x) return m;
50         if(jh[m]<x) l=m;
51         else r=m;
52     }
53 }
54 
55 int main()
56 {
57     scanf("%d",&N);
58     for(int i=1;i<=N;i++)
59     {
60         scanf("%d %d %d",&a[i],&b[i],&c[i]);
61         jh[2*i-1]=a[i],jh[2*i]=b[i];
62     }
63     
64     sort(jh+1,jh+2*N+1);
65     for(int i=1;i<=2*N;i++)
66         if(jh[i+1]!=jh[i]) jh[++M]=jh[i];
67     for(int i=1;i<=N;i++)
68     {
69         if(a[i]>b[i]) swap(a[i],b[i]);
70         UpDate(bfind(a[i]),bfind(b[i]),c[i],1,M,1);
71     }
72     int m=(1+M)>>1;
73     cout<<Query(1,m,2,h[1])+Query(m,M,3,h[1]);
74     return 0;
75 }

View Code

技术分享

p2061[usaco07open]cityhorizons（区间问题，线段树/堆）(代码片段)

题目描述FarmerJohnhastakenhiscowsonatriptothecity!Asthesunsets,thecowsgazeatthecityhorizonandobservethebeautifulsilhouettesformedbytherectangularbuildings.TheentirehorizonisrepresentedbyanumberlinewithN(1 查看详情

p2061[usaco07open]cityhorizons（区间问题，线段树/堆）(代码片段)

bzoj_1654_[usaco2007open]cityhorizon城市地平线_扫描线

BZOJ_1654_[Usaco2007Open]CityHorizon城市地平线_扫描线DescriptionN个矩形块，交求面积并.Input*Line1:Asingleinteger:N*Lines2..N+1:Inputlinei+1describesbuildingiwiththreespace-separatedintegers:A_i,B_i,andH_iOutput*Line1:T 查看详情

poj3693后缀数组重复次数最多的连续重复子串

MaximumrepetitionsubstringTimeLimit: 1000MS MemoryLimit: 65536KTotalSubmissions: 10612 Accepted: 3277DescriptionTherepetitionnumberofastringisdefinedasthemaximumnumber&nb 查看详情

前端学习（3277）：promise的使用

查看详情

bzoj1645/p2061[usaco07open]城市的地平线cityhorizon（扫描线）(代码片段)

P2061[USACO07OPEN]城市的地平线CityHorizon扫描线扫描线简化版流程（本题为例）：把一个矩形用两条线段（底端点的坐标，向上长度，添加$or$删除）表示，按横坐标排序$upd:$本题的底端点坐标简化为$(x,0)$蓝后对纵坐标建一棵线段树... 查看详情

bzoj1645:[usaco2007open]cityhorizon城市地平线线段树+hash

bzoj题面什么鬼啊……题目大意：有一个初始值均为0的数列，n次操作，每次将数列(ai,bi-1)这个区间中的数与ci取max，问n次后元素和离散化，然后建立线段树，每次修改在区间上打max标记即可#include<iostream>#include<cstdio>#incl... 查看详情

bzoj3277串(代码片段)

https://www.lydsy.com/JudgeOnline/problem.php?id=3277把多个串插入广义后缀自动机中，建出parent树，在树上做set启发式合并,记录下每一个前缀在不同串出现的次数，再对每个串暴力匹配一遍，求出答案即可.复杂度O(nlogn)1#include<algorithm>2... 查看详情

如何解决 .net 核心构建错误 NETDSDK1061 和警告 MSB3277

】如何解决.net核心构建错误NETDSDK1061和警告MSB3277【英文标题】：Howtoresolve.netcorebuilderrorNETDSDK1061andwarningMSB3277【发布时间】：2019-03-0206:01:49【问题描述】：我遇到了问题，我的AspNetCore.App-metapackage引用的EntityFrameworkCore(2.1.2)版本低... 查看详情

bzoj3277串

TimeLimit: 10Sec MemoryLimit: 128MBSubmit: 568 Solved: 233Description字符串是oi界常考的问题。现在给定你n个字符串，询问每个字符串有多少子串（不包括空串）是所有n个字符串中至少k个字符串的子串（注意包... 查看详情

[bzoj3277]串广义后缀自动机(代码片段)

3277:串TimeLimit: 10Sec MemoryLimit: 128MBSubmit: 811 Solved: 329[Submit][Status][Discuss]Description字符串是oi界常考的问题。现在给定你n个字符串，询问每个字符串有多少子串（不包括空串）是所有n个字符串中至少k... 查看详情

mm32f3277micropython实验板设计和软件测试(代码片段)

§01设计要求在制作测试MM32F3277-MicroPython最小电路板测试了基于MM32F3277的MicroPython测试板。也可以看到它的时钟是不需要。下面设计一个适应于面包板进行测试实验的MicroPython测试板。一、资源设置1、MicroPython支持模块下面使用... 查看详情

设计带有sd卡的mm32f3277micropython实验板(代码片段)

简介：本文测试了基于MM32F3277下的MicroPython电路板设计。其中包含有SD卡接口，常用外设接口等。验证了现在的移植的MicroPython的对文件的基本操作功能。关键词：MM32F3277，MicroPython，SD卡 §01设计背景一、MM32F32... 查看详情

制作灵动单片机mm32f3277测试版(代码片段)

...了在Windows7下安装基于MM32-LINK开发软件。设计制作了MM32F3277的测试电路板，并对如何正确从MM32-LINK将调试电缆连接至MM32F3277开发板进行介绍。需要保证编程电流长度以及线序都满足要求，才能够正确完成程序高速下载。关... 查看详情

bzoj3277:串

Description字符串是oi界常考的问题。现在给定你n个字符串，询问每个字符串有多少子串（不包括空串）是所有n个字符串中至少k个字符串的子串（注意包括本身）。Solution出现$k$次的问题比较好解决,我们构出$parent$树,然后在上... 查看详情

制作测试mm32f3277-micropython最小电路板(代码片段)

简介：设计制作了基于MM32F3277的MicroPython测试电路，下载了来自于SeekFree已知的MicroPython，证明它可以完成正常使用。关键词：MM32F3277，MicroPython，快速制版 §01参考设计一、设计背景在前天已经通过以... 查看详情

bzoj3277:串(代码片段)

以下全部是笔记，不要看了注意：要求的不是"有多少不同的子串是..."，相同的要重复计算贡献。例如：32acaac答案是311第一个串中两个a都出现了两次，c出现了两次，所以第一个的答案是3广义后缀自动机模板。各个串连起来中间... 查看详情

hdu3277marriagematchiii(并查集+二分答案+最大流sap)拆点，经典

MarriageMatchIIITimeLimit:10000/4000MS(Java/Others) MemoryLimit:32768/32768K(Java/Others)TotalSubmission(s):1581 AcceptedSubmission(s):464ProblemDescripti 查看详情