刷题记录:牛客NC24309Overplanting (Silver)
传送门:牛客
题目描述:
Farmer John has purchased a new machine that is capable of planting grass within any rectangular region of
his farm that is "axially aligned" (i.e., with vertical and horizontal sides). Unfortunately, the machine
malfunctions one day and plants grass in not one, but N (1 <= N <= 1000) different rectangular regions, some
of which may even overlap.
Given the rectangular regions planted with grass, please help FJ compute the total area in his farm that is
now covered with grass.
输入:
2
0 5 4 1
2 4 6 2
输出:
20
一道扫描线的题目.但是因为数据范围比较小,所以可以使用二维差分来做
但是我既然是在线段树的题单中碰到了这道题,当然就直接用线段树做啦.毕竟用线段树来实现扫描线本身就是对二维差分做法的优化
对于扫描线算法,网上有大量博客对此进行讲解,此处就不在赘述了
为各位在提供一个有关这道题的另一种题面(不要换了题面就不会做了):
有一个数列，初始值均为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;
}line[maxn];
bool cmp(Line A,Line B) {if(A.y==B.y) return A.l<B.l;else return A.y<B.y;
}
int n;vector<int>v;
int Getid(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 x1=read(),y1=read(),x2=read(),y2=read();line[++cnt].l=x1;line[cnt].r=x2;line[cnt].y=min(y1,y2);line[cnt].cate=1;line[++cnt].l=x1;line[cnt].r=x2;line[cnt].y=max(y1,y2);line[cnt].cate=-1;v.push_back(x1);v.push_back(x2);}sort(v.begin(),v.end());v.erase(unique(v.begin(),v.end()),v.end());int Size=v.size();build(1,Size,1);sort(line+1,line+2*n+1,cmp);int ans=0;int pre=0;for(int i=1;i<=2*n-1;i++) {int x=Getid(line[i].l),x2=Getid(line[i].r);update(x,x2,line[i].cate,1);ans+=query(1,Size,1)*(line[i+1].y-line[i].y);}cout<<ans<<endl;return 0;
}
下面是具体的代码部分(不维护pushdownpushdownpushdown版):
#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*8];
struct Line{int l,r,y,cate;
}line[maxn];
bool cmp(Line A,Line B) {if(A.y==B.y) return A.l<B.l;else return A.y<B.y;
}
int n;
void build(int l,int r,int rt) {tree[rt].l=l;tree[rt].r=r;tree[rt].cov=0;tree[rt].len=0;if(l==r) return ;int mid=(l+r)>>1;build(lson);build(rson);
}
vector<int>v;
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 rt,int val) {if(tree[rt].l==l&&tree[rt].r+1==r) {tree[rt].cov+=val;if(tree[rt].cov!=0) 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,ls,val);else if(l>=mid+1) update(l,r,rs,val);else update(l,mid+1,ls,val),update(mid+1,r,rs,val);pushup(rt);
}
int Getid(int x) {return lower_bound(v.begin(),v.end(),x)-v.begin()+1;
}
signed main() {n=read();int cnt=0;for(int i=1;i<=n;i++) {int x1=read(),y1=read(),x2=read(),y2=read();line[++cnt].l=x1;line[cnt].r=x2;line[cnt].y=min(y1,y2);line[cnt].cate=1;line[++cnt].l=x1;line[cnt].r=x2;line[cnt].y=max(y1,y2);line[cnt].cate=-1;v.push_back(x1);v.push_back(x2);}sort(v.begin(),v.end());v.erase(unique(v.begin(),v.end()),v.end());int Size=v.size();build(1,Size,1);sort(line+1,line+2*n+1,cmp);int ans=0;int pre=0;for(int i=1;i<=2*n-1;i++) {int x=Getid(line[i].l),x2=Getid(line[i].r);update(x,x2,1,line[i].cate);ans+=tree[1].len*(line[i+1].y-line[i].y);}cout<<ans<<endl;return 0;
}