例题
不管是一个技术还是一个算法，最好的学习场景就是一次实践、一道题目。这次要根据线段树中的扩展，看一题经典的线段树扫描法。题目链接
题目大意：
给出n个矩形的左下角坐标和右上角坐标。然后求这些矩形面积的总和。如下图：
给出了三个矩形
我们把这幅图处理一下，然后下图中的红色部分的面积就是我们需要求得面积总和（可能有点丑）
红色部分的面积就是需要求得的面积总和
条件：0<=x<=100000、0<=y<=100000、n<=100
解析（先看懂解决方法，再进行实践扩展）
首先我们把这个“畸形”分成若干个矩形，如下图
畸形分割
如上五块面积之和就是需要求的面积大小。
我们拿出其中一块的面积，矩形面积=x轴对应长度（下面称为宽度）×y轴对应长度（下面称为高度）
在接收坐标的时候，我们把这几条黄线都存下来，用如下结构体（y_start和y_end的位置如上图）
struct Line {
double y_end,y_start,x; //y_start是y轴下顶点坐标，y_end是y轴的上顶点坐标，x是x轴的坐标
int flag; //标记，矩形左边是1，右边是-1
}line[2*maxn];
然后我们模拟一个扫描的行为——其实就是黄线从左到右的for循环
在扫描的过程中，很容易求得，line[i+1].x-line[i].x就是这个矩形的宽度。那高度怎么求呢？
然后线段树就来了
线段树维护的y轴区间
这次我们把这个“畸形”按y轴分割成5个部分。这五个部分投影到y轴也就是5个线段——位置从下标0到下标5
我们发现上面我们要求的高度，无非就是这5个线段的组合而已。比如，第①个面积的高度是线段1-4，第②个面积的高度是线段0-4，第③个面积的高度是线段0-3，第④个面积的高度是线段0-5，第⑤个面积的高度是线段2-5。当然有一个大前提，这个线段没有单位，每一段都是一个抽象的概念，比如线段0-1的实际长度可能是12，线段1-2的实际长度可能是29
那怎么知道现在扫描到的这个矩形的高度是哪几个线段的组合呢？？
我们对这5段建立线段树（当然测试用例肯定不止5段线段）
struct node {
int l,r,flag; //l、r表示线段的起点和终点，flag表示是否需要把这一段加入到面积的计算中
double len; //长度
}tree[100*maxn];
void build(int i,int l,int r){ //建立线段树
tree[i].l = l;
tree[i].r = r;
tree[i].flag = tree[i].len = 0; //长度和标记默认为0
if(l+1 == r) return;
int mid = (l+r)/2;
build(2*i,l,mid); //递归建树，直到叶节点位置，直到每一段都是最小单位
build(2*i+1,mid,r);
}
岔开一下，到这里，说明一下为什么要用线段树，因为前面存在一个标记，矩形的左边是1，右边是-1，标记为1表示下面这部分y轴的相对距离（这部分线段）都是要加入到面积的计算的。如果矩形的面积为0，那这部分线段就不需要加入面积的计算。所以它需要在扫描的过程中不断的更新每一个线段的状态。所以用线段树来实现
代码不难，可能更新的过程需要解释一下
void calcul(int i) {
if(tree[i].flag) tree[i].len = y_axis[tree[i].r] - y_axis[tree[i].l]; //如果标记为>=1，则长度等于这个线段的高度
else if(tree[i].l+1 == tree[i].r) tree[i].len = 0; //如果为叶子阶段，且标记为0，则置1
else tree[i].len = tree[2*i].len + tree[2*i+1].len; //如果不是叶子节点，那么此节点的长度就是子节点的长度之和
}
void updata(int i,int l,int r,int flag) {
if(tree[i].l>r || tree[i].r<l) return; //不符合条件
if(tree[i].l>=l && tree[i].r<=r) { //这个段在指定下标所在段之间
tree[i].flag += flag; //累加标记，1-1=0可以抵消标记
calcul(i); //计算这个一段的有效长度（能加入面积计算的长度）
return;
}
updata(2*i,l,r,flag); //如果这个段不在指定下标所在的段之间，就遍历子节点
updata(2*i+1,l,r,flag);
calcul(i);
}
…………
for(int i=0;i<t-1;i++){ //扫描这几条线
startY = lower_bound(y_axis, y_axis+t, line[i].y_start) - y_axis; //找到这条线的下顶点所表示的线段下标
endY = lower_bound(y_axis, y_axis+t, line[i].y_end) - y_axis; //找到这条线的上顶点所表示的线段下标
updata(1,startY,endY,line[i].flag); //更新这个两个下标所对应的线段的状态，line[I].flag传入的是1或者-1
area += tree[1].len * (line[i+1].x - line[i].x); //面积累加
}
…………
在边有重叠的情况下，y轴有重叠需要去重，因为建树叶子节点需要唯一。而x轴不需要去重，可以思考一下为啥~
重叠边的情况
去重过程
for(int i=1;i<t;i++)
if(y_axis[i-1] != y_axis[I])
y_axis[len++] = y_axis[I];
build(1,0,--len); //--len表示去重后的长度，也就是建树需要的长度
去重后只需要维护四个线段
总结
写了很长的解析部分，总结一下思路把
对于这个畸形，作与y轴平行的线，将这个“畸形”分成5个部分，通过从左往右扫描这几条线，取得相应的面积。
每到达一条线时，（前面已经维护了x=a这条边的y轴起点和终点），将对应的边映射到线段树中。然后更新线段树。如果这是左边，那么flag=1，在更新时，主要是把这条边加入到面积的计算中。如果这是右边，那么flag=0，在更新时，主要是把这条边从面积的计算中移除。
那是不是每次扫描到右边都没有面积，因为都是在处理移除操作。
并不是。比如，扫描到第一条线是左边，将线段0-2加入面积计算。扫描到第二条线是左边，将线段3-4加入到面积的计算中，总线段是(0-2) + (3-4)。扫描到第三条边是右边，将线段0-2移除面积计算。但是在移除的同时我们发现第二次扫描的线段3-4还在面积的计算中，所以第三次扫描计算面积时，总线段是3-4
扫描到最后，取得的就是总的面积
AC代码
#include <iostream>
#include <string>
#include <algorithm>
#define maxn 110
using namespace std;
struct node {
int l,r,flag; //l、r表示线段的起点和终点，flag表示是否需要把这一段加入到面积的计算中
double len; //长度
}tree[100*maxn];
struct Line {
double y_end,y_start,x; //y_start是y轴下顶点坐标，y_end是y轴的上顶点坐标，x是x轴的坐标
int flag; //标记，矩形左边是1，右边是-1
}line[2*maxn];
double y_axis[2*maxn];
int cmp(Line a,Line b){
return a.x<b.x;
}
void build(int i,int l,int r){ //建立线段树
tree[i].l = l;
tree[i].r = r;
tree[i].flag = tree[i].len = 0; //长度和标记默认为0
if(l+1 == r) return;
int mid = (l+r)/2;
build(2*i,l,mid); //递归建树，直到叶节点位置，直到每一段都是最小单位
build(2*i+1,mid,r);
}
void calcul(int i) {
if(tree[i].flag) tree[i].len = y_axis[tree[i].r] - y_axis[tree[i].l]; //如果标记为>=1，则长度等于这个线段的高度
else if(tree[i].l+1 == tree[i].r) tree[i].len = 0; //如果为叶子阶段，且标记为0，则置1
else tree[i].len = tree[2*i].len + tree[2*i+1].len; //如果不是叶子节点，那么此节点的长度就是子节点的长度之和
}
void updata(int i,int l,int r,int flag) {
if(tree[i].l>r || tree[i].r<l) return; //不符合条件
if(tree[i].l>=l && tree[i].r<=r) { //这个段在指定下标所在段之间
tree[i].flag += flag; //累加标记，1-1=0可以抵消标记
calcul(i); //计算这个一段的有效长度（能加入面积计算的长度）
return;
}
updata(2*i,l,r,flag); //如果这个段不在指定下标所在的段之间，就遍历子节点
updata(2*i+1,l,r,flag);
calcul(i);
}
int main(){
double x1,y1,x2,y2,area;
int t,startY,endY,cas=1,n,len;;
while(scanf("%d",&n)==1 && n) {
t=0;len=1;area=0;
for(int i=0;i<n;i++) {
scanf("%lf %lf %lf %lf",&x1,&y1,&x2,&y2);
y_axis[t] = y1;
y_axis[t+1] = y2;
line[t].flag = 1;
line[t+1].flag = -1;
line[t].x = x1;
line[t+1].x = x2;
line[t].y_start = line[t+1].y_start = y1;
line[t].y_end = line[t+1].y_end = y2;
t += 2;
}
sort(y_axis,y_axis+t);
sort(line,line+t,cmp);
for(int i=1;i<t;i++) //y轴去重，x轴不需要去重，可以思考一下为啥
if(y_axis[i-1] != y_axis[I])
y_axis[len++] = y_axis[I];
build(1,0,--len); //--len表示去重后的长度，也就是建树需要的长度
printf("Test case #%d\n",cas++);
for(int i=0;i<t-1;i++){ //扫描这几条线
startY = lower_bound(y_axis, y_axis+t, line[i].y_start) - y_axis; //找到这条线的下顶点所表示的线段下标
endY = lower_bound(y_axis, y_axis+t, line[i].y_end) - y_axis; //找到这条线的上顶点所表示的线段下标
updata(1,startY,endY,line[i].flag); //更新这个两个下标所对应的线段的状态，line[I].flag传入的是1或者-1
area += tree[1].len * (line[i+1].x - line[i].x); //面积累加
}
printf("Total explored area: %0.2lf\n\n",area);
}
return 0;
}
扩展
题意
给出n个矩形的左下角坐标和右上角坐标（和上面的一样）。每个矩形编号从1~n。现在要进行若干次查询，每次查询的格式如3 1 4 5，第一个3表示后面跟了3个编号，需要求的是这3个编号的矩形的面积总和
所以这题和上面这题的区别是，上面是求所有矩形面积的总和。而这题需要求其中几个编号的矩形的面积总和。
解析
在上面的代码的基础上，增加一个结构体，用来存储所有的节点
struct rec {
int x1,y1,x2,y2;
}cache[2*maxn];
然后每次查询的时候重新建树即可
AC代码
#include <iostream>
#include <string>
#include <algorithm>
#define maxn 110
using namespace std;
struct node {
int l,r,flag,len; //l、r表示线段的起点和终点，flag表示是否需要把这一段加入到面积的计算中
}tree[100*maxn];
struct Line {
int y_end,y_start,x; //y_start是y轴下顶点坐标，y_end是y轴的上顶点坐标，x是x轴的坐标
int flag; //标记，矩形左边是1，右边是-1
}line[2*maxn];
struct rec {
int x1,y1,x2,y2;
}cache[2*maxn];
int y_axis[2*maxn];
int cmp(Line a,Line b){
return a.x<b.x;
}
void build(int i,int l,int r){ //建立线段树
tree[i].l = l;
tree[i].r = r;
tree[i].flag = tree[i].len = 0; //长度和标记默认为0
if(l+1 == r) return;
int mid = (l+r)/2;
build(2*i,l,mid); //递归建树，直到叶节点位置，直到每一段都是最小单位
build(2*i+1,mid,r);
}
void calcul(int i) {
if(tree[i].flag) tree[i].len = y_axis[tree[i].r] - y_axis[tree[i].l]; //如果标记为>=1，则长度等于这个线段的高度
else if(tree[i].l+1 == tree[i].r) tree[i].len = 0; //如果为叶子阶段，且标记为0，则置1
else tree[i].len = tree[2*i].len + tree[2*i+1].len; //如果不是叶子节点，那么此节点的长度就是子节点的长度之和
}
void updata(int i,int l,int r,int flag) {
if(tree[i].l>r || tree[i].r<l) return; //不符合条件
if(tree[i].l>=l && tree[i].r<=r) { //这个段在指定下标所在段之间
tree[i].flag += flag; //累加标记，1-1=0可以抵消标记
calcul(i); //计算这个一段的有效长度（能加入面积计算的长度）
return;
}
updata(2*i,l,r,flag); //如果这个段不在指定下标所在的段之间，就遍历子节点
updata(2*i+1,l,r,flag);
calcul(i);
}
int main(){
int t,startY,endY,cas=1,n,m,r,k,len,area;
while (cin>>n>>m){
if (n==0 && m==0) break;
for (int i=1; i<=n; i++)
scanf("%d %d %d %d",&cache[i].x1,&cache[i].y1,&cache[i].x2,&cache[i].y2);
printf("Case %d:\n",cas++);
for (int i=1; i<=m; i++) {
scanf("%d",&r);
t=0;len=1;area=0;
for (int j=0; j<r; j++) {
scanf("%d",&k);
y_axis[t] = cache[k].y1;
y_axis[t+1] = cache[k].y2;
line[t].flag = 1;
line[t+1].flag = -1;
line[t].x = cache[k].x1;
line[t+1].x = cache[k].x2;
line[t].y_start = line[t+1].y_start = cache[k].y1;
line[t].y_end = line[t+1].y_end = cache[k].y2;
t += 2;
}
sort(y_axis,y_axis+t);
sort(line,line+t,cmp);
for(int i=1;i<t;i++) //y轴去重，x轴不需要去重，可以思考一下为啥
if(y_axis[i-1] != y_axis[i])
y_axis[len++] = y_axis[i];
build(1,0,--len); //--len表示去重后的长度，也就是建树需要的长度
for(int i=0;i<t-1;i++){ //扫描这几条线
startY = lower_bound(y_axis, y_axis+t, line[i].y_start) - y_axis; //找到这条线的下顶点所表示的线段下标
endY = lower_bound(y_axis, y_axis+t, line[i].y_end) - y_axis; //找到这条线的上顶点所表示的线段下标
updata(1,startY,endY,line[i].flag); //更新这个两个下标所对应的线段的状态，line[I].flag传入的是1或者-1
area += tree[1].len * (line[i+1].x - line[i].x); //面积累加
}
printf("Query %d: %d\n",i,area);
}
printf("\n");
}
return 0;
}
网友评论