二叉树回顾

在计算机科学中，二叉树（英语：Binary tree ）是每个节点最多只有两个分支（即不存在分支度大于 2 的节点）的树结构。通常分支被称作“左子树”或“右子树”。 二叉树的分支具有左右次序，不能随意颠倒。——wikipedia

递归定义：

  • 由有限个结点构成的集合，此集合可以为空
  • 二叉树的根节点下可分为两个子树,称为左子树和右子树，左子树右子树亦称二叉树

存储实现：数组顺序实现，以 1 做根节点，记父亲结点为 i , 则左孩子的标号为 2i , 右孩子的标号为 2i+1

二叉树实现：链式结构数组

（1）静态写法

1
2
3
4
5
6
7
8
9
10
11
12
struct Node{
	int data;//数据域
	int l;//左孩子位置(存入的是左支在数组中的位置)
	int r;//右孩子位置(存入的是右支在数组中的位置)
}tree[maxn];
int cnt=0;//统计二叉树中已经建立了多少节点
int nextree(int val){//新建节点
	tree[cnt].data=val;//数据域
	tree[cnt].l=-1;//叶子节点左孩子为空
	tree[cnt].r=-1;//叶节子点右孩子为空
	return cnt++;//返回此时为第几个节点，同时新增节点
}

（2）动态写法

见下文线段树动态开点

线段树引入

题目：10000 个正整数，编号 1 到 10000 ，用 A[1],A[2],...,A[10000] 表示

要求一：无任何修改，求数组编号从 L 到 R 的所有和

  • 方法一：数组每个单元存储一个数 S[i]=A[i] ，然后进行 L+R-1 次求和
  • 方法二：数组每个单元存储前缀和 S[i]=A[i]+S[i-1] ，然后进行一次 A[L]-A[R-1] 计算

要求二：在数组编号为 L 的数上 +C

方法一：数组每个单元存储一个数 S[i]=A[i] ，只需要将 S[L]+C

方法二：数组每个单元存储前缀和 S[i]=A[i]+S[i-1] ，从 S[L] 开始直到编号 10000 都 +C

综上：

方法一 方法二
A[L]+=C 修改一次 修改 10000-L+1 次
求和A[L..R] L+R-1次计算 一次计算

从上表可以看出，方法一修改快求和慢，方法二求和快修改慢。那有没有一种结构修改和求和都相对较快的呢？一个完美的答案就是线段树。

其实树状数组的区间修改、区间查询也可以做到，两个都要会用

线段树结构

定义：线段树是一种基于二分与分治思想的二叉树结构， 用于在区间上进行信息统计

特点：

  • 线段树的每个节点都代表一个区间。

  • 线段树具有唯一的根，代表的是区间的整个统计信息，如 [1,n]

  • 线段树的每个叶节点代表一个长度为 1 的元区间 [x,x]

  • 对于每个内部节点 [l,r] ，它的左子节点 [l,mid] ， 右子节点是 [mid+1,r]（ mid=(l+r)>>1 )

线段树建立

问题一：如何分解子区间

首先是讲原始子区间的分解，假定给定区间 [L,R] ，只要 L<R ，线段树就会把它继续分裂成两个区间。

首先计算 mid=(L+R)/2 ，左子区间为 [L,mid] ，右子区间为 [mid+1,R] ，然后如果子区间不满足条件就递归分解。以区间 [1..13] 的分解为例，分解结果见下图：

问题二：给定区间 [L,R] 如何分解到上述区间

分解方法一：自下而上便于理解

先考虑树的最下层，将所有在区间 [2,12] 内的点选中，然后若相邻的点的直接父节点是同一个，那么就用这个父节点代替这两个节点（父节点在上一层）。这样操作之后本层最多剩下两个节点（两端的节点）

若最左侧被选中的节点是它父节点的右子树，那么这个节点会被剩下，若最右侧被选中的节点是它的父节点的左子树，那么这个节点会被剩下中间的所有节点都被父节点取代。

对最下层处理完之后，考虑它的上一层，继续进行同样的处理。

下图为 n=13 的线段树，区间 [2,12] ，按照上面的叙述进行操作的过程图：

最后 [2,12] 区间在 n=13 的线段树中被分解成：[2,12]=[2]+[3,4]+[5,7]+[8,10]+[11,12]

分解方法二：自上而下便于计算

首先对于区间 [1,13] ，计算 (1+13)/2=7 ，于是将区间 [2,12] 切割成了 [2,7] 和 [8,12]

其中 [2,7] 处于节点 [1,7] 的位置，[2,7]<[1,7] 所以继续分解，计算 (1+7)/2=4 , 于是将 [2,7] 切割成 [2,4] 和 [5,7]

[5,7] 处于节点 [5,7] 的位置，所以不用继续分解，[2,4] 处于区间 [1,4] 的位置，所以继续分解成 [2] 和 [3,4]

最后 [2]<[1,2] ，所以计算 (1+2)/2=1 ，将 [2] 用 1 切割，左侧为空，右侧为 [2]

当然程序是递归计算的，不是一层一层计算的，上图只是演示的计算方法，不是真正的计算顺序

问题三：复杂度分析和空间开多大

时间复杂度 空间复杂度
O(logn) O(n)

线段树将长 n 的区间分为不超过 4n 个的子区间

时间复杂度无论是修改还是查询都是选择约 2log(R-L+1) 个拼成区间 [L,R]

空间复杂度 O(n+n/2+…+1)=O(2n-1)=O(n)

线段树是一种二叉树可以像一般的树那样写成结构体，指针什么的。它的最大优点是可以用数组来实现树形结构可以大大简化代码。
简单的记法： 足够的空间=数组大小n的四倍
实际上：足够的空间=(n向上扩充到最近的2的某个次方)的两倍

假设数组长度为 5 ，就需要 5 先扩充成 8 ，8*2=16，线段树需要 16 个元素。如果数组元素为 8 ，那么也需要 16 个元素。所以线段树需要的空间是 n 的两倍到四倍之间的某个数，一般就开 4n 的空间就好，如果空间不够，可以自己算好最大值来省点空间

模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#define maxn 1e7//元素的总个数
int a[maxn];//用来存原数组下标 
struct segtree{ 
	int l,r;//标记节点左右区间的值 
	int val;//标记该节点统计到的信息，以下模板以求和为例 
}t[maxn<<2];//开四倍，堆式建树（数组存储法）

void build(int root,int l,int r){//传入根节点下标和要读入建树的区间 
	t[root].l=l,t[root].r=r;//标记该节点要记录的区间 
	if(l==r){//如果左右相等了就到了叶子节点，也就是到了递归基 
		t[root].val=a[l];//此时root的节点域即当前长度为1的位置 
		return;
	}
	int mid=(l+r)>>1;//没到叶子节点，继续往下建树，二分法将问题对半劈 
	build(root*2,l,mid);//转化为[l..mid],并建立左子树 
	build(root*2+1,mid+1,r);//转化为[mid+1..r],并建立右子树 
	t[root].val=t[root*2].val+t[root*2+1].val;//合并得到的左右子树的答案 
}

线段树操作

修改以加值，查询以求和为例。线段树单点查询完全可以用区间查询实现，若是查询 a[x] 那么就查询 [x,x] 区间即可。

单点修改、区间查询

假设这 13 个数为 1 ，2 ，3 ，4 ，1 ，2 ，3 ，4 ，1 ，2 ，3 ，4 ，1 。在区间之后标上该区间的数字之和

假设把 A[6]+7 ，那么 [6],[5,6],[5,7],[1,7],[1,13] 这些区间全部都需要 +7 。其余所有区间都不用动。于是这颗线段树中单点修改最多修改 5 个线段树元素（每层一个）

1
2
3
4
5
6
7
8
9
10
11
//要在a[id]的值加上score 
void update(int root,int id,int score){//单点修改 
	if(t[root].l==t[root].r){//左==右即为递归基 
		t[root].val+=score;//更新单点 
		return ;
	}
	int mid=(t[root].l+t[root].r)>>1;//二分，从中间分开 
	if(id<=mid)update(root*2,id,score);//待更新的位置比中点小，即为左子树 
	else update(root*2+1,id,score);//否则就是在右子树 
	t[root].val=t[root*2].val+t[root*2+1].val;//合并左右子树更新答案 
}

仍以这 13 个数 1 ，2 ，3 ，4 ，1 ，2 ，3 ，4 ，1 ，2 ，3 ，4 ，1 为例，如果要计算 [2,12] 的和，按照之前的算法：[2,12]=[2]+[3,4]+[5,7]+[8,10]+[11,12] 即 29=2+7+6+7+7

1
2
3
4
5
6
7
8
9
10
int query(int root,int l,int r){//区间查询 
	if(l<=t[root].l&&r>=t[root].r)//待查询的区间小于树管辖的区间
	return t[root].val;//递归基直接返回 
	//否则，还得分
	int mid=(t[root].l+t[root].r)>>1;//二分,从中间分开 
	int ans=0;
	if(l<=mid)ans+=query(root*2,l,r);//如果待查询的区间比中点小 ,说明查询涉及左子树，往下递归 
	if(r>mid)ans+=query(root*2+1,l,r);//如果待查询的区间比中点大, 说明查询涉及右子树，往下递归 
	return ans;//返还答案 
}

模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include<bits/stdc++.h>
using namespace std;

const int maxn=1e7;//元素的总个数
int a[maxn];//用来存原数组下标,从1开始存储

struct segtree{ 
	int l,r;//标记节点左右区间的值 
	int val;//标记该节点统计到的信息，以下模板以求和为例 
}t[maxn<<2];//开四倍，堆式建树（数组存储法）

void build(int root,int l,int r){//传入根节点下标和要读入建树的区间 
	t[root].l=l,t[root].r=r;//标记该节点要记录的区间 
	if(l==r){//如果左右相等了就到了叶子节点，也就是到了递归基 
		t[root].val=a[l];//此时root的节点域即当前长度为1的位置 
		return;
	}
	int mid=(l+r)>>1;//没到叶子节点，继续往下建树，二分法将问题对半劈 
	build(root*2,l,mid);//转化为[l..mid],并建立左子树 
	build(root*2+1,mid+1,r);//转化为[mid+1..r],并建立右子树 
	t[root].val=t[root*2].val+t[root*2+1].val;//合并得到的左右子树的答案 
}

//要在a[id]的值加上score 
void update(int root,int id,int score){//单点修改 
	if(t[root].l==t[root].r){//左==右即为递归基 
		t[root].val+=score;//更新单点 
		return ;
	}
	int mid=(t[root].l+t[root].r)>>1;//二分，从中间分开 
	if(id<=mid)update(root*2,id,score);//待更新的位置比中点小，即为左子树 
	else update(root*2+1,id,score);//否则就是在右子树 
	t[root].val=t[root*2].val+t[root*2+1].val;//合并左右子树更新答案 
} 

int query(int root,int l,int r){//区间查询 
	if(l<=t[root].l&&r>=t[root].r)//待查询的区间小于树管辖的区间
	return t[root].val;//递归基直接返回 
	//否则，还得分
	int mid=(t[root].l+t[root].r)>>1;//二分,从中间分开 
	int ans=0;
	if(l<=mid)ans+=query(root*2,l,r);//如果待查询的区间比中点小 ,说明查询涉及左子树，往下递归 
	if(r>mid)ans+=query(root*2+1,l,r);//如果待查询的区间比中点大, 说明查询涉及右子树，往下递归 
	return ans;//返还答案 
} 

signed main()
{
	int n;cin>>n;
	for(int i=1;i<=n;i++)//存值
	cin>>a[i];
	build(1,1,n);//建树

	int c,k;//a[c]+k
	cin>>c>>k;
	update(1,c,k);

	int l,r;//a[l...r]求和
	cin>>l>>r;
	query(1,l,r);
	return 0;
}

区间修改、区间查询

  • 直接修改时间复杂度高达 O(N)

因为你修改 n 个点的话，就需要把这 n 个点所在的区间全部更新

  • 引入 lazy_tag ，继续用分治的手法来解决修改与查询

lazy_tag 含义：本区间已经被更新过了但是子区间却没有被更新过并记录被修改的信息

具体操作：

  • 找到区间中全部都是要修改的点在线段树中的区间，修改这一段区间的所有点并标记，若标记过就累加标记的修改信息
  • 待查询到某段区间时若存在标记就将标记信息加入并下传到子区间

比如线段树维护区间是 [1,10] 。现在要让区间 [2,8] 的值都 +5 ，将 [2,8] 区间再第一层分割直至满足真包含于要修改的区间然后打上标记代表需要修改然后就结束修改操作。

当我查询区间 [6,8] 时发现第一层区间 [6,8] 存在标记那么就将区间的的值 +5 然后下传标记给子区间。这样可以发现如果我没查询到带有标记的区间，那么这个区间的子区间永远都不会修改知道查询到才会更新修改信息。如此便减少了无用的区间修改操作，进而加快了速度

注意：修改操作只是将区间打上标记，查询时遇到标记再更新区间并下传标记

核心思想：我们可以直接修改一个大区间的值，并不需要修改他的子节点，等我们需要单独提出该子节点信息的时候再下传这个懒标记并修改这个子节点

由于用时在更新值，所以区间修改，区间查询都要下传 lazy_tag ，所以模板都发生了变化

在 update 操作中多了打上标记，并在查询时遇到标记是多了调用 spread() 下传函数用来更新区间信息并下传标记

模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include<bits/stdc++.h>
using namespace std;

const int maxn=1e7;
int a[maxn];

//定义，结构上有了小小的改变 
struct segtree{
	int l,r;//标记为该节点统计的区间 
	int val;//统计的结果值 
	int add;//add的延迟操作 
}t[maxn<<2];

//建树 
void build(int root,int l,int r){
	t[root].l=l,t[root].r=r,t[root].add=0;//关键：不初始化遇到跑多次就可能出错
	if(l==r){//递归基，区间不再划分 
		t[root].val=a[l];//统计值 
		return ;//回退 
	}
	int mid=(l+r)>>1;
	build(root*2,l,mid);
	build(root*2+1,mid+1,r);
	t[root].val=t[root<<1].val+t[root<<1|1].val;//统计父节点答案
}

//下传lazy_tag 
void spread(int p){//p是要更新节点的父元素 
	if(t[p].add){
		t[p*2].val+=t[p].add*(t[p*2].r-t[p*2].l+1);//更新左子节点 
		t[p*2+1].val+=t[p].add*(t[p*2+1].r-t[p*2+1].l+1);//更新右子节点
		t[p*2].add+=t[p].add;//下传延迟标记至左子节点 
		t[p*2+1].add+=t[p].add;//下穿延迟标记至右子节点 
		t[p].add=0;//清空父亲的延时标记 
	}
}

//区间修改 
void update(int root,int l,int r,int x){
	if(l<=t[root].l&&r>=t[root].r){//递归基，无需划分问题的时候 
		t[root].val+=x*(t[root].r-t[root].l+1);//直接在和上添加答案 
		t[root].add+=x;//同时打上标记 
		return ;//返回		
	}
	spread(root);
	int mid=(t[root].l+t[root].r)/2;
	if(l<=mid)update(root*2,l,r,x);//左边小于右边，与左子节点有关 
	if(r>=mid+1)update(root*2+1,l,r,x);//右边比中点大，与右子节点有关 
	t[root].val=t[root*2].val+t[root*2+1].val;//更新父节点 
}

//区间查询 
int query(int root,int l,int r){
	if(l<=t[root].l&&r>=t[root].r)//递归基，无需划分 
	return t[root].val;//直接返回
	spread(root);//下传延时标记 
	int mid=(t[root].l+t[root].r)>>1;//取中点
	int ans=0;
	if(l<=mid)ans+=query(root*2,l,r);
	if(r>=mid+1)ans+=query(root*2+1,l,r);
	return ans; 
}

signed main(){
	int n;cin>>n;
	for(int i=1;i<=n;i++)
	cin>>a[i];

	build(1,1,n);

	//将a[l]~a[r]都+k
	int l,r,k;
	cin>>l>>r>>k;
	update(1,l,r,k);

	//查询a[l..r]
	int l,r;
    cin>>l>>r;
	query(1,l,r);
	return 0;
}

变式：修改操作改为乘法

模板题：有长为 n 的数列，不妨设为 a1,a2,⋯,an 有如下三种操作形式：

  • 把数列中的一段数全部乘一个值；
  • 把数列中的一段数全部加一个值；
  • 询问数列中的一段数的和，由于答案可能很大，你只需输出这个数模 P 的值。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn=100005;

ll n,m,p;
ll a[maxn],sum[4*maxn];
ll add[4*maxn],mul[4*maxn];

void build(ll root,ll l,ll r){
	add[root]=0;
	mul[root]=1;
	if(l==r){
		sum[root]=a[l];
		return;
	}
	ll mid=(l+r)>>1;
	build(root<<1,l,mid);
	build(root<<1|1,mid+1,r);
	sum[root]=(sum[root<<1]+sum[root<<1|1])%p;
}

void spread_mul(ll root,ll l,ll r){
	mul[root<<1]=(mul[root<<1]*mul[root])%p;
	mul[root<<1|1]=(mul[root<<1|1]*mul[root])%p;
	add[root<<1]=(add[root<<1]*mul[root])%p;
	add[root<<1|1]=(add[root<<1|1]*mul[root])%p;
	sum[root<<1]=(sum[root<<1]*mul[root])%p;
	sum[root<<1|1]=(sum[root<<1|1]*mul[root])%p;
	mul[root]=1;
}

void spread_add(ll root,ll l,ll r){
	ll mid=(l+r)>>1;
	add[root<<1]=(add[root<<1]+add[root])%p;
	add[root<<1|1]=(add[root<<1|1]+add[root])%p;
	sum[root<<1]=(sum[root<<1]+(mid-l+1)*add[root]%p)%p;
	sum[root<<1|1]=(sum[root<<1|1]+(r-mid)*add[root]%p)%p;
	add[root]=0;
}

void mul_lazy(ll root,ll l,ll r,ll x,ll y,ll k){
	if(l>=x&&r<=y){
		add[root]=(1ll*add[root]*k)%p;
		mul[root]=(mul[root]*k)%p;
		sum[root]=(sum[root]*k)%p;
		return ;
	}
	ll mid=(l+r)>>1;
	if(mul[root]!=1)  
	spread_mul(root,l,r);
	if(add[root]!=0)  
	spread_add(root,l,r);
	if(x<=mid)  
	mul_lazy(root<<1,l,mid,x,y,k);
	if(y>mid)  
	mul_lazy(root<<1|1,mid+1,r,x,y,k);
	sum[root]=(sum[root<<1]+sum[root<<1|1])%p;
}

void add_lazy(ll root,ll l,ll r,ll x,ll y,ll k){
	if(l>=x&&r<=y){
		add[root]=(add[root]+k)%p;
		sum[root]=(sum[root]+(r-l+1)*k%p)%p;
		return;
	}
	ll mid=(l+r)>>1;
	if(mul[root]!=1)  
	spread_mul(root,l,r);
	if(add[root]!=0)  
	spread_add(root,l,r);
	if(x<=mid)  
	add_lazy(root<<1,l,mid,x,y,k);
	if(y>mid)  
	add_lazy(root<<1|1,mid+1,r,x,y,k);
	sum[root]=(sum[root<<1]+sum[root<<1|1])%p;
}

ll query(ll root,ll l,ll r,ll x,ll y){
	if(l>=x&&r<=y)
	  return sum[root];
	ll ans=0,mid=(l+r)>>1;
	if(mul[root]!=1)  
	spread_mul(root,l,r);
	if(add[root]!=0)  
	spread_add(root,l,r);
	if(x<=mid)  
	ans=(ans+query(root<<1,l,mid,x,y))%p;
	if(y>mid)  
	ans=(ans+query(root<<1|1,mid+1,r,x,y))%p;
	return ans;
}

signed main()
{
	cin>>n>>p;
	for(ll i=1;i<=n;++i)
	cin>>a[i];
	build(1,1,n);
	cin>>m;
	ll x,y,k,s;
	for(ll i=1;i<=m;++i){
		cin>>s;
		if(s==1){
			cin>>x>>y>>k;
			mul_lazy(1,1,n,x,y,k);
		}
		else if(s==2){
			cin>>x>>y>>k;
			add_lazy(1,1,n,x,y,k);
		}
		else{
			cin>>x>>y;
			cout<<query(1,1,n,x,y)<<endl;
		}
	}
	return 0;
}

线段树动态开点

如果空间要求实在跟不上题目的要求，比如元素的 n 真的很大，开四倍的话爆内存就需要抛弃堆式建树，考虑前驱与后继动态开点(由循秩变为循位置）

本质：就是用哪里开哪里，每次访问之前看看是否为空，为空就新建一个节点

没用过待检测

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
//多少个元素就开多少个点
//结构体的实现 
int root,tot;//根节点和即时节点 
struct segtree{
	int l,r;
	int val;
}t[maxn];

//建立新节点 
int build(){//开新的节点 
	tot++;
	t[tot].l=t[tot].r=t[tot].val=0;//初始化为0
	return tot;//返回位置（指针） 
}

//修改，建树，增加新节点
void insert(int root,int l,int r,int id,int score){
//根节点，左右支，要更改的节点，要更改的值 
	if(l==r){//递归基 
		t[root].val+=x;//修改数据域 
		return ;
	}
	int mid=(l+r)>>1;//二分 
	if(id<=mid){//进入[l,mid] 
		if(!t[root].l)t[root].l=build();//未开辟则开辟新节点 
		insert(t[root].l,l,mid,id,score);
	}
	else{//[mid,r]
		if(!t[root].r)t[root].r=build();
		insert(t[root].r,mid+1,id,score);
	}
	t[root].val=t[t[root].l].val+t[t[root].r].val;//合并更新当前父节点的数据域 
} 

//区间查询 
int query(int root,int l,int r,int ql,int qr){//qr,ql是待查询的区间 
	if(qr<=l&&qr>=r)//递归基直接返还 
	return t[root].val;
	int ans=0;
	int mid=(l+r)>>1;
	if(ql<=mid)ans+=query(t[root].l,l,mid,ql,qr);//统计左子树 
	if(qr>=mid+1)ans+=query(t[root].r,mid+1,r,ql,qr);//统计右子树 
	return ans;//返还答案 
}

线段树应用：扫描线

参考博客 先看转载的博客就好了，看了也不会用

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include<bits/stdc++.h>
#define INF 99999999
using namespace std;
 
const int MAX=200+10;
int mark[MAX<<2];//记录某个区间的下底边个数
double sum[MAX<<2];//记录某个区间的下底边总长度
double hash[MAX];//对x进行离散化,否则x为浮点数且很大无法进行线段树 
 
//以横坐标作为线段(区间),对横坐标线段进行扫描
//扫描的作用是每次更新下底边总长度和下底边个数,增加新面积 
struct seg{//线段 
	double l,r,h;
	int d;
	seg(){}
	seg(double x1,double x2,double H,int c):l(x1),r(x2),h(H),d(c){}
	bool operator<(const seg &a)const{
		return h<a.h;
	}
}s[MAX];
 
void Upfather(int n,int left,int right){
	if(mark[n])sum[n]=hash[right+1]-hash[left];//表示该区间整个线段长度可以作为底边 
	else if(left == right)sum[n]=0;//叶子结点则底边长度为0(区间内线段长度为0) 
	else sum[n]=sum[n<<1]+sum[n<<1|1];
}
 
void Update(int L,int R,int d,int n,int left,int right){
	if(L<=left && right<=R){//该区间是当前扫描线段的一部分,则该区间下底边总长以及上下底边个数差更新 
		mark[n]+=d;//更新底边相差差个数 
		Upfather(n,left,right);//更新底边长 
		return;
	}
	int mid=left+right>>1;
	if(L<=mid)Update(L,R,d,n<<1,left,mid);
	if(R>mid)Update(L,R,d,n<<1|1,mid+1,right);
	Upfather(n,left,right);
}
 
int search(double key,double* x,int n){
	int left=0,right=n-1;
	while(left<=right){
		int mid=left+right>>1;
		if(x[mid] == key)return mid;
		if(x[mid]>key)right=mid-1;
		else left=mid+1;
	}
	return -1;
}
 
int main(){
	int n,num=0;
	double x1,x2,y1,y2;
	while(cin>>n,n){
		int k=0;
		for(int i=0;i<n;++i){
			cin>>x1>>y1>>x2>>y2;
			hash[k]=x1;
			s[k++]=seg(x1,x2,y1,1);
			hash[k]=x2;
			s[k++]=seg(x1,x2,y2,-1);
		}
		sort(hash,hash+k);
		sort(s,s+k);
		int m=1;
		for(int i=1;i<k;++i)//去重复端点 
		    if(hash[i] != hash[i-1])hash[m++]=hash[i];
        double ans=0;
        //memset(mark,0,sizeof mark);
        //memset(sum,0,sizeof sum);如果下面是i<k-1则要初始化,因为如果对第k-1条线段扫描时会使得mark,sum为0才不用初始化的 
		for(int i=0;i<k;++i){//扫描线段 
			int L=search(s[i].l,hash,m);
			int R=search(s[i].r,hash,m)-1;
			Update(L,R,s[i].d,1,0,m-1);//扫描线段时更新底边长度和底边相差个数
			ans+=sum[1]*(s[i+1].h-s[i].h);//新增加面积 
		}
		printf("Test case #%d\nTotal explored area: %.2lf\n\n",++num,ans);
	}
	return 0;
}
/*
这里注意下扫描线段时r-1:int R=search(s[i].l,hash,m)-1;
计算底边长时r+1:if(mark[n])sum[n]=hash[right+1]-hash[left];
解释:假设现在有一个线段左端点是l=0,右端点是r=m-1
则我们去更新的时候,会算到sum[1]=hash[mid]-hash[left]+hash[right]-hash[mid+1]
这样的到的底边长sum是错误的,why?因为少算了mid~mid+1的距离,由于我们这利用了
离散化且区间表示线段,所以mid~mid+1之间是有长度的,比如hash[3]=1.2,hash[4]=5.6,mid=3
所以这里用r-1,r+1就很好理解了 
*/

模板题：给定平面上若干矩形,求出被这些矩形覆盖过至少两次的区域的面积.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
#include<bits/stdc++.h>
#define ls rt<<1
#define rs rt<<1|1
using namespace std;

const int maxn = 1010;

struct LINE{
	double l,r,h;//线段的左右端点的坐标和高度
	int flag; //flag=1表示下边，flag=-1表示上边
}line[maxn<<2];

struct Tree{
	int l,r,cnt;//l，r表示以rt为根节点的左右区间，cnt记录当前重叠几次
	double s,ss;//s表示重叠1次及以上的长度，ss表示重叠2次及以上的长度
}p[maxn<<3];//该范围至少要开*8的空间

int n,t;//矩形的个数和测试样例数
double x[maxn<<3];//记录离散化后x的坐标数组
 
bool cmp(LINE A,LINE B){//自定义扫描线比较函数
	return A.h<B.h;
}
 
void build(int l,int r,int rt){//建立线段树
	p[rt].l=l;p[rt].r=r;
	p[rt].cnt=p[rt].s=p[rt].ss=0;

	if(l==r) return ;//递归基返回
    //建立子节点
	int m=(l+r) >> 1;
	build(l,m,ls);
	build(m+1,r,rs);
}
 
void pushup(int rt){//向上传递
	if(p[rt].cnt)p[rt].s=x[p[rt].r+1]-x[p[rt].l];//如果线段被扫描线扫到了则更新扫到的线段长度 
	else if(p[rt].l== p[rt].r)p[rt].s=0;
	else p[rt].s=p[ls].s+p[rs].s;//如果没被扫到 则从以前扫过的线段更新

    //面积覆盖两次及以上，则等于该区间内的线段长，左端点=右端点则线段长度为0，面积覆盖1次或以上，则等于左右区间的和（保证两次及以上）
    //面积覆盖0次或以上，则等于左右覆盖两次或以上的区间和
	if(p[rt].cnt>1) p[rt].ss=x[p[rt].r+1]-x[p[rt].l];//本来就被扫两次了直接更新
	else if(p[rt].r==p[rt].l)p[rt].ss=0;
	else if(p[rt].cnt==1) p[rt].ss=p[ls].s+p[rs].s;//这是第二次被扫到所以加上从子节点的被扫过总线段长度（因为加上这次保证了线段被扫两次及以上）
	else p[rt].ss=p[ls].ss+p[rs].ss;////如果没被扫到 则从以前扫过两次及以上的线段更新
}
 
void update(int l,int r,int rt,int flag){//更新区间数据
	if(p[rt].l==l &&p[rt].r==r){//找到该线段
		p[rt].cnt+=flag;
		pushup(rt);
		return;
	}
	int m=(p[rt].l+p[rt].r)>>1;
	if(r<=m)update(l,r,ls,flag);
	else if(l>m) update(l,r,rs,flag);
	else{//劈开分别找
		update(l,m,ls,flag);
		update(m+1,r,rs,flag);
	}
	pushup(rt);//向上传回更新rt父节点
}
 
int main(){
	//scanf("%d",&t);
    cin>>t;
	while(t--){
		//scanf("%d",&n);
        cin>>n;
		double x1,x2,y1,y2;
		int tot=0;
		for(int i=0;i<n;i++){//记录线段
			//scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
            cin>>x1>>y1>>x2>>y2;
			x[tot]=x1;x[tot+1]=x2;
			line[tot].h=y1;line[tot+1].h=y2;
			line[tot].flag=1;line[tot+1].flag=-1;
			line[tot].l=line[tot+1].l=x1;
			line[tot].r=line[tot+1].r=x2;
			tot+=2;
		}

        //排序保证线段从下向上扫，x轴上的坐标从小到大
		sort(x,x+tot);
		sort(line,line+tot,cmp);
        //离散化，去掉重复的坐标
		int k=1;
		for(int i =1; i<tot;i++){ 
			if(x[i]!=x[i-1]) x[k++]=x[i];
		}

        //建立相应的线段树
		build(0,k-1,1);

		double ans=0;//统计面积
		for(int i=0;i<tot-1;i++){//将线段存入线段树进行维护更新
			int l=lower_bound(x,x+k,line[i].l)-x;
			int r=lower_bound(x,x+k,line[i].r)-x-1;
			update(l,r,1,line[i].flag);
			ans+=(line[i+1].h-line[i].h)*p[1].ss;//每插入一次就更新一次，计算总面积用p[i]的ss
		}
		printf("%.2lf\n",ans);
	}
	return 0;
}