请在学习之前有一定的线段树基础
在一些题中，它总会给你一些矩形，之后让你求总覆盖面积。
它的难点在于，有重叠面积，如果只是罗列情况，那么只会一事无成。
所以说，这里就引进了扫描线做法；
其实它的原理很简单，只是底*高而已，只是分段求解；
而问题大概的图就是这样
根据我刚刚说的分段求解和底*高，那么我们就可以推测出扫描线是什么了
它是由矩形的上边和下边构成，并记录其左右端点和其所在的纵坐标；
图中标红的即为扫描线，那么我们用它做什么？
根据 S=a*h，那么我们可以将扫描线按纵坐标排序，这样分步求解。
这是扫描线的储存
struct node{ int x,y;//左右端点坐标 int h;//还是按 扫描线写，这个是y轴坐标 int d;//标记这个线是不是上界或下界 }s[maxn<<3];//扫描线
那么便可以得到高，即
s[i+1].h-s[i].h
之后考虑存底，只需要用线段树维护即可；
当扫描线为下界时，应当将扫描线所在区域加入线段树，而当为上界时再减去即可；
由于底边过大，不可能全部建树，这里给出了离散化做法，还有动态开点做法之后将会提到
由于找不到最合适的模板题，只能拿这个来充数P2061 [USACO07OPEN]城市的地平线City Horizon
scanf("%d",&n); for(int i=1,a,b,h;i<=n;i++){ scanf("%d%d%d",&a,&b,&h); ls[++cent]=a;//其实是用来离散化的 s[cent]=(node){a,b,0,1}; ls[++cent]=b; s[cent]=(node){a,b,h,-1}; } sort(ls+1,ls+1+cent);//离散化初始 sort(s+1,s+1+cent);ls[++m]=ls[1]; for(int i=2;i<=cent;i++){ if(ls[i]!=ls[i-1]) ls[++m]=ls[i];//去重 }
这便是简单的离散化，当然，你也可以排序后用unique函数，得到m和ls数组，这个可以网上查询，这里便不再赘述
之后是线段树
void push_up(int l,int r,int p){ if(mark[p]) tree[p].sum=ls[r]-ls[l];//如何避免少减？ else if(l==r) tree[p].sum=0; else tree[p].sum=tree[le(p)].sum+tree[re(p)].sum; } void up_date(int p,int d,int L,int R){ int l=tree[p].l,r=tree[p].r; if(l>=L&&r<=R){ mark[p]+=d; push_up(l,r,p); return ; } if(r-1==l) return ; int mid=l+r>>1; if(mid>=L) up_date(le(p),d,L,R); if(mid<R) up_date(re(p),d,L,R); push_up(l,r,p); }
这里的代码是我根据多种方面得出，但是仍由问题，即代码所说的，因为在线段数中 l 是可以等于 r 的，但是线段的长度必须由两个不同的数得出，这是不行的
所以，我们可以先建出一颗空树
void build(int l,int r,int p){ tree[p].l=l; tree[p].r=r; tree[p].sum=0; if(l==r-1) return ; int mid=l+r>>1; build(l,mid,le(p)),build(mid,r,re(p));/*注意，mid在左子树和右子树中都有出现，所以在 叶子节点，r=l+1，这个也是对return 的解释*/ }
所以说，这样便避免了这个问题，不过请读者注意这些点，这些便是易错的小细节
build(1,m,1); for(int i=1;i<=cent;i++){ int l=search(s[i].x,ls);//二分寻找离散化位置 int r=search(s[i].y,ls); up_date(1,s[i].d,l,r);// 用线段树更新sum，即矩形底边 rt+=(ll)tree[1].sum*1ll*(s[i+1].h-s[i].h); }
这里是主函数的计算，而search有解释，也可以用lower_bound，推荐提前处理出来，否则可能会提高时间复杂度，这不是我们所期望的
这样的做法不易错是真的，这里给出二分search做法
int search(int pur,int* x){ int l=1,r=m; while(l<r){ int mid=l+r>>1; if(x[mid]<pur) l=mid+1; else r=mid; } return l; }
这便是整个过程，这里给出code
Code
#include<bits/stdc++.h> #define ll long long #define maxn 40007 #define le(x) x<<1 #define re(x) x<<1|1 using namespace std; int n,cent,m,mark[maxn<<4]; int ls[maxn<<3]; ll rt; struct tr{ ll sum; int l,r; }tree[maxn<<4]; struct node{ int x,y;//左右端点坐标 int h;//还是按 扫描线写，这个是y轴坐标 int d;//标记这个线是不是上界或下界 }s[maxn<<3];//扫描线 bool operator <(node a,node b){ return a.h<b.h; } void push_up(int l,int r,int p){ if(mark[p]) tree[p].sum=ls[r]-ls[l];//如何避免少减？ else if(l==r) tree[p].sum=0; else tree[p].sum=tree[le(p)].sum+tree[re(p)].sum; } void up_date(int p,int d,int L,int R){ int l=tree[p].l,r=tree[p].r; if(l>=L&&r<=R){ mark[p]+=d; push_up(l,r,p); return ; } if(r-1==l) return ; int mid=l+r>>1; if(mid>=L) up_date(le(p),d,L,R); if(mid<R) up_date(re(p),d,L,R); push_up(l,r,p); } void build(int l,int r,int p){ tree[p].l=l; tree[p].r=r; tree[p].sum=0; if(l==r-1) return ; int mid=l+r>>1; build(l,mid,le(p)),build(mid,r,re(p));/*注意，mid在左子树和右子树中都有出现，所以在 叶子节点，r=l+1，这个也是对return 的解释*/ } int search(int pur,int* x){ int l=1,r=m; while(l<r){ int mid=l+r>>1; if(x[mid]<pur) l=mid+1; else r=mid; } return l; } int main(){ // freopen("cin.in","r",stdin); scanf("%d",&n); for(int i=1,a,b,h;i<=n;i++){ scanf("%d%d%d",&a,&b,&h); ls[++cent]=a;//其实是用来离散化的 s[cent]=(node){a,b,0,1}; ls[++cent]=b; s[cent]=(node){a,b,h,-1}; } sort(ls+1,ls+1+cent);//离散化初始 sort(s+1,s+1+cent);ls[++m]=ls[1]; for(int i=2;i<=cent;i++){ if(ls[i]!=ls[i-1]) ls[++m]=ls[i];//去重 } build(1,m,1); for(int i=1;i<=cent;i++){ int l=search(s[i].x,ls);//二分寻找离散化位置 int r=search(s[i].y,ls); up_date(1,s[i].d,l,r);// 用线段树更新sum，即矩形底边 rt+=(ll)tree[1].sum*1ll*(s[i+1].h-s[i].h); } cout<<rt<<endl; return 0; }
7.24 补充：
题目背景
小卡买到了一套新房子，他十分的高兴，在房间里转来转去。
题目描述
晚上，小卡从阳台望出去，“哇~~~~好多星星啊”，但他还没给其他房间设一个窗户，天真的小卡总是希望能够在晚上能看到最多最亮的星星，但是窗子的大小是固定的，边也必须和地面平行。这时小卡使用了超能力（透视术）知道了墙后面每个星星的位置和亮度，但是小卡发动超能力后就很疲劳，只好拜托你告诉他最多能够有总和多亮的星星能出现在窗口上。
输入输出格式
输入格式：
本题有多组数据，第一行为T 表示有T组数据T<=10
对于每组数据
第一行3个整数n，W，H，（n<=10000,1<=W,H<=1000000）表示有n颗星星，窗口宽为W，高为H。
接下来n行，每行三个整数xi，yi，li 表示星星的坐标在（xi，yi），亮度为li。（0<=xi,yi<2^31)
输出格式：
T个整数，表示每组数据中窗口星星亮度总和的最大值。
这道题的一个关键点是，将星星作为一个窗户的左下角（其实是为了不出现负数），将每一个星星都创一个窗户，之后寻找重叠部分
解释
看这个图，这是两个相交的情况，矩形左下角是星星，然后如果有重叠部分，那么我们要贴着相交部分的上边和右边建一个窗户，那么就可以盖住这两个星星，
类比到所有星星是一样的，我们只要将矩形附上权值即可，用扫描线寻找。
但是这个边框不是不能包含星星吗？所以我们需要处理一些小细节，将矩形右边的横坐标减去1，也就是提前减去，再将扫描线上端-1，这就处理了边界问题；
并且在sort的时候当横坐标相同时，将加上的排在前面。
这个细节请一定要理解，否则wa了也不好调（因为不给数据），代码我会做上标记。
矩形权值直接附在扫描线上即可；
上一道例题中，我用离散化解决了范围大的问题，这里我们介绍动态开点做法；
首先不需要在意太多的离散化细节是一个优点，干干的介绍不是非常简洁，所以我直接附上代码讲解：
#include<bits/stdc++.h> #define maxn 10007 using namespace std; int t,n,w,h,cnt,lim,root; struct node{ int x,l,r,w,d; }a[maxn<<3];//扫描线 struct tree{ int le,ri,w,tag; }tr[5000007];//动态开点的不同，le和ri记录的是左端点和右端点的p值 //tr记住稍微大一点 （别 MLE 了 ），反正不会错 template<typename type_of_scan> inline void scan(type_of_scan &x){ type_of_scan f=1;x=0;char s=getchar(); while(s<'0'||s>'9') f=s=='-'?-1:1,s=getchar(); while(s>='0'&&s<='9') x=(x<<3)+(x<<1)+s-'0',s=getchar(); x*=f; } bool operator <(node x,node y){ return x.x==y.x?x.d>y.d:x.x<y.x; }//sort的细节*** inline void push_down(int p,int k){ if(!tr[p].le) tr[p].le=++cnt;//没点开点 if(!tr[p].ri) tr[p].ri=++cnt; tr[tr[p].le].w+=k,tr[tr[p].ri].w+=k; tr[tr[p].le].tag+=k,tr[tr[p].ri].tag+=k; } void add(int nl,int nr,int l,int r,int &p,int k){ if(!p) p=++cnt;//没点开点 if(nl<=l&&nr>=r){ tr[p].w+=k,tr[p].tag+=k; return ; } if(tr[p].tag) push_down(p,tr[p].tag);tr[p].tag=0; int mid=(l+r)>>1; if(nl<=mid) add(nl,nr,l,mid,tr[p].le,k); if(nr>mid) add(nl,nr,mid+1,r,tr[p].ri,k); tr[p].w=max(tr[tr[p].le].w,tr[tr[p].ri].w); }//与线段树相同 inline void work(){ int ans=0;memset(tr,0,sizeof tr); scan(n);scan(w),scan(h); for(int i=1,x,y,v;i<=n;i++) scan(x),scan(y),scan(v),lim=max(x+w+1,lim),//lim是线段树范围 a[(i<<1)-1]=(node){x,y,y+h-1,v,1},//强行转换格式，-1的细节** a[i<<1]=(node){x+w-1,y,y+h-1,v,-1};//细节** sort(a+1,a+1+2*n);//细节** for(int i=1;i<=2*n;i++){ add(a[i].l,a[i].r,1,lim,root,a[i].w*a[i].d); ans=max(ans,tr[root].w);//直接用整棵树更新就好啦 } printf("%d ",ans); } int main(){ scan(t); while(t--) work(); return 0; }
扫描线2种方法都已经讲完，可以再找一些题练习一下；