刷题记录:牛客NC25078[USACO 2007 Ope S]City Horizon

传送门:牛客

题目描述:

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 Ai through Bi along the horizon (1 ≤ Ai < Bi ≤ 1,000,000,000) and has height Hi (1 ≤ 
Hi ≤ 1,000,000,000). Determine the area, in square units, of the aggregate silhouette formed by all N buildings.
输入:
4
2 5 1
9 10 4
6 8 2
4 6 3
输出;
16

经典的多个矩形覆盖求总面积问题.需要使用扫描线算法进行解决.

对于扫描线算法,网上有大量博客对此进行讲解,此处就不在赘述了

为各位在提供一个有关这道题的另一种题面(不要换了题面就不会做了):

有一个数列，初始值均为0，他进行N次操作，每次将数列[ai,bi)这个区间中所有比Hi小的数改为Hi，他想知道N次操作后数列中所有元素的和。

看了这个题面有没有感觉扫描线的一些神奇之处??感觉有点积分的思想在那里了,反正我刚开始看到这道题(当我学完扫描线之后),我当时仍然是不知道怎么做的,根本就没有往扫描线那里想,还在想该怎么维护这道题.

优化&巧妙的想法:对于这种只需要区间[1,n]的维护值来说,我们建立线段树的时候可以不使用pushdown(因为我们根本不需要关注子节点是怎么样的),在子节点pushup的时候将父节点对子节点的lazy加上即可.
注意,此方法在我看来并不具有很强的意义,虽然省去了对子节点的维护,码量减少了,但是因为这种方式大大的修改了模板,会导致出现一写奇奇怪怪的错误甚至思维上的混乱,但是在平时可以挑战一下,这样改变常规的做法可以大大增强自己对线段树的理解

下面是具体的代码部分(标准版维护版):

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define root 1,n,1
#define ls rt<<1
#define rs rt<<1|1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {ll x=0,w=1;char ch=getchar();for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';return x*w;
}
#define int long long
#define maxn 1000000
const double eps=1e-8;
#define	int_INF 0x3f3f3f3f
#define ll_INF 0x3f3f3f3f3f3f3f3f
struct Segment_tree{int l,r,cov,lazy;
}tree[maxn*8];
struct Line{int l,r,y,cate;bool operator < (const Line &rhs) const {return y<rhs.y;}
}line[maxn];
int n;vector<int>v;
int Get_id(int x) {return lower_bound(v.begin(),v.end(),x)-v.begin()+1;
}
void build(int l,int r,int rt) {tree[rt].l=l;tree[rt].r=r;if(l==r) return ;int mid=(l+r)>>1;build(lson);build(rson);
}
void pushup(int rt) {tree[rt].cov=min(tree[ls].cov,tree[rs].cov);
}
void change(int rt,int val) {tree[rt].cov+=val;tree[rt].lazy+=val;
}
void pushdown(int rt) {change(ls,tree[rt].lazy);change(rs,tree[rt].lazy);tree[rt].lazy=0;
}
void update(int l,int r,int val,int rt) {if(tree[rt].l==l&&tree[rt].r+1==r) {change(rt,val);return ;}if(tree[rt].lazy) pushdown(rt);int mid=(tree[rt].l+tree[rt].r)>>1;if(r<=mid+1) update(l,r,val,ls);else if(l>=mid+1) update(l,r,val,rs);else update(l,mid+1,val,ls),update(mid+1,r,val,rs);pushup(rt);
}
int query(int l,int r,int rt) {if(tree[rt].l==l&&tree[rt].r+1==r) {if(tree[rt].cov) return v[r-1]-v[l-1];else if(tree[rt].l==tree[rt].r) return 0; }if(tree[rt].lazy) pushdown(rt);int mid=(tree[rt].l+tree[rt].r)>>1;if(r<=mid+1) return query(l,r,ls);else if(l>=mid+1) return query(l,r,rs);else return query(l,mid+1,ls)+query(mid+1,r,rs);
}
signed main() {n=read();int cnt=0;for(int i=1;i<=n;i++) {int a=read(),b=read(),h=read();line[++cnt].l=a;line[cnt].r=b;line[cnt].y=0;line[cnt].cate=1;line[++cnt].l=a;line[cnt].r=b;line[cnt].y=h;line[cnt].cate=-1;v.push_back(b);v.push_back(a);}sort(line+1,line+2*n+1);sort(v.begin(),v.end());v.erase(unique(v.begin(),v.end()),v.end());int Size=v.size();build(1,Size,1);int ans=0;for(int i=1;i<=2*n-1;i++) {int x1=Get_id(line[i].l),x2=Get_id(line[i].r);update(x1,x2,line[i].cate,1);ans+=query(1,Size,1)*(line[i+1].y-line[i].y);}cout<<ans<<endl;return 0;
}

下面是具体的代码部分(不维护$pushdown$版):

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define root 1,n,1
#define ls rt<<1
#define rs rt<<1|1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {ll x=0,w=1;char ch=getchar();for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';return x*w;
}
#define int long long
#define maxn 1000000
const double eps=1e-8;
#define	int_INF 0x3f3f3f3f
#define ll_INF 0x3f3f3f3f3f3f3f3f
struct Segment_tree{int l,r,cov,len;
}tree[maxn*4];
int n;vector<int>v;
int Get_id(int x) {return lower_bound(v.begin(),v.end(),x)-v.begin()+1;
}
struct Line{int l,r,y,cate;bool operator < (const Line &rhs) const {return y<rhs.y;}
}line[maxn];
void build(int l,int r,int rt) {tree[rt].l=l;tree[rt].r=r;if(l==r) return ;int mid=(l+r)>>1;build(lson);build(rson);
}
void pushup(int rt) {if(tree[rt].cov) tree[rt].len=v[tree[rt].r]-v[tree[rt].l-1];else tree[rt].len=tree[ls].len+tree[rs].len;
}
void update(int l,int r,int val,int rt) {if(tree[rt].l==l&&tree[rt].r+1==r) {tree[rt].cov+=val;if(tree[rt].cov) tree[rt].len=v[r-1]-v[l-1];else pushup(rt);return ;}int mid=(tree[rt].l+tree[rt].r)>>1;if(r<=mid+1) update(l,r,val,ls);else if(l>=mid+1) update(l,r,val,rs);else update(l,mid+1,val,ls),update(mid+1,r,val,rs);pushup(rt);
}
signed main() {n=read();int cnt=0;for(int i=1;i<=n;i++) {int a=read(),b=read(),h=read();line[++cnt].l=a;line[cnt].r=b;line[cnt].y=0;line[cnt].cate=1;line[++cnt].l=a;line[cnt].r=b;line[cnt].y=h;line[cnt].cate=-1;v.push_back(b);v.push_back(a);}sort(line+1,line+2*n+1);sort(v.begin(),v.end());v.erase(unique(v.begin(),v.end()),v.end());int Size=v.size();build(1,Size,1);int ans=0;for(int i=1;i<=2*n-1;i++) {int x1=Get_id(line[i].l),x2=Get_id(line[i].r);update(x1,x2,line[i].cate,1);ans+=tree[1].len*(line[i+1].y-line[i].y);}cout<<ans<<endl;return 0;
}