线段树学习笔记（持续更新）

关于线段树

线段树是一种支持单点修改，区间修改，区间操作，区间查找的优秀数据结构，通常能将时间复杂度中的一个n变为log，极大优化了算法效率

对比树状数组

总而言之，能用树状数组解决的问题一般都能使用线段树解决，但树状数组不能解决的线段树大概率 能解决，但树状数组运行速度更快，实现难度更小，实际运用起来要根据场景选择使用

线段树的基本用法

使用线段树前要先建树（废话
对于所有的线段树而言，它们的所有基本思想都能用四个字代替
——分而治之
眼熟吧，因为线段树就是分治思想的一种实现
通过将一个大区间的询问分解为一个个小区间的询问，再将小区间的内容合并为大区间的内容，每当修改时打上标记，询问时再根据标记更新，保证了极低的时间复杂度
这么说可能有点抽象，我来举个实际点的例子：

对于这样一个序列a
2 3 4 3

我们的需求是在logn的时间复杂度下得到区间L到R的最大值
第一步：建树
我们在每两个相邻节点上方构建个新的点，储存点权为两个相邻节点的的最大值
这样原序列就变为了

重复操作，最终得到了线段树

如要查询区间1-3的最大值，只需要查询1-2和3-3的最大值再取最大值即可
最终答案是4

如要将区间1-3的值全部修改为0，也只需要修改1-2和3-3的值即可
问题来了，我们需要从1-2向下修改1-1和2-2的值吗？
答，不需要
我们只需要对每个点记录一个lazy标记，每次访问到这个点时再修改为0即可

线段树升级！

看题：线段树2
大致题意：维护一个线段树，使得它能够支持区间加法，区间乘法，区间求和

一眼丁真，鉴定为维护两个lazytag，一个乘法一个加法，访问到这个点的时候先加上再乘
.
…
…
真的是这样吗？
我们发现，对于一个运算
1*3+3=6
但若按照我们之前的思路,运算就变成了
(1+3)*3=12
显然不对！
所以我们应该先乘上再加!
.
…
…
就对了吗？
肯定不止！
我们发现对于两个lazytag而言，乘法标记还会对先前的加法乘法标记产生影响
所以对于往下pushdown时，还要对加法的懒标记乘上乘法标记
然后就可以愉快的AC了~

ylrn大佬的题解 Orz

#include<bits/stdc++.h>
#define int long long
using namespace std;

const int MAXN = 200005;

int n, m, p;
int a[MAXN];
int sum[MAXN * 4];

int ls(int u) {	return u << 1;}
int rs(int u) {	return u << 1 | 1;}

int tag_add[MAXN * 4], tag_mul[MAXN * 4];
void push_up(int u)
{
	sum[u] = (sum[ls(u)] + sum[rs(u)]) % p;
}
void push_down(int u, int l, int r)
{
	int mid = (l + r) >> 1;
	
	sum[ls(u)] = (sum[ls(u)] * tag_mul[u]) % p;
	sum[rs(u)] = (sum[rs(u)] * tag_mul[u]) % p;
	
	tag_add[ls(u)] = (tag_add[ls(u)] * tag_mul[u]) % p;
	tag_add[rs(u)] = (tag_add[rs(u)] * tag_mul[u]) % p;
	tag_mul[ls(u)] = (tag_mul[ls(u)] * tag_mul[u]) % p;
	tag_mul[rs(u)] = (tag_mul[rs(u)] * tag_mul[u]) % p;
	tag_mul[u] = 1;
	
	sum[ls(u)] = (sum[ls(u)] + tag_add[u] * (mid - l + 1)) % p;
	sum[rs(u)] = (sum[rs(u)] + tag_add[u] * (r - mid)) % p;
	
	tag_add[ls(u)] = (tag_add[ls(u)] + tag_add[u]) % p;
	tag_add[rs(u)] = (tag_add[rs(u)] + tag_add[u]) % p;
	tag_add[u] = 0;
	
}
void build(int u, int l, int r)
{
	tag_mul[u] = 1, tag_add[u] = 0;
	if(l == r)
	{
		sum[u] = a[l];
		return;
	}
	int mid = (l + r) >> 1;
	build(ls(u), l, mid);
	build(rs(u), mid + 1, r);
	push_up(u);
}
void update_add(int u, int l, int r, int x, int y, int k)
{
	if(x <= l && r <= y)
	{
		sum[u] = (sum[u] + k * (r - l + 1)) % p;
		tag_add[u] = (tag_add[u] + k) % p;
		return;
	}
	if(tag_add[u] || tag_mul[u] != 1) 
		push_down(u, l, r);
	int mid = (l + r) >> 1;
	if(x <= mid) update_add(ls(u), l, mid, x, y, k);
	if(y > mid) update_add(rs(u), mid + 1, r, x, y, k);
	push_up(u);
}
void update_mul(int u, int l, int r, int x, int y, int k)
{
	if(x <= l && r <= y)
	{
		sum[u] = (sum[u] * k) % p;
		tag_add[u] = (tag_add[u] * k) % p;
		tag_mul[u] = (tag_mul[u] * k) % p;
		return;
	}
	if(tag_add[u] || tag_mul[u] != 1) 
		push_down(u, l, r);
	int mid = (l + r) >> 1;
	if(x <= mid) update_mul(ls(u), l, mid, x, y, k);
	if(y > mid) update_mul(rs(u), mid + 1, r, x, y, k);
	push_up(u);
}

int query(int u, int l, int r, int x, int y)
{
	int res = 0;
	if(tag_add[u] || tag_mul[u] != 1) 
		push_down(u, l, r);
	if(x <= l && r <= y)
	{
		return sum[u];
	}
	int mid = (l + r) >> 1;
	if(x <= mid) res = (res + query(ls(u), l, mid, x, y)) % p;
	if(y > mid) res = (res + query(rs(u), mid + 1, r, x, y)) % p;
	return res;
}



signed main()
{
	
	scanf("%lld%lld", &n, &m);
	scanf("%lld", &p);
	for(int i = 1; i <= n; i++)
	{
		scanf("%lld", &a[i]);
		a[i] %= p;
	}
	build(1, 1, n);
	
	while(m--)
	{
		int opt, x, y, k;
		scanf("%lld", &opt);
		if(opt == 1)
		{
			scanf("%lld%lld%lld", &x, &y, &k);
			update_mul(1, 1, n, x, y, k);
		}
		else if(opt == 2)
		{
			scanf("%lld%lld%lld", &x, &y, &k);
			update_add(1, 1, n, x, y, k);
		}
		else if(opt == 3)
		{
			scanf("%lld%lld", &x, &y);
			printf("%lld\n", query(1, 1, n, x, y) % p);
		}
	}
	
return 0;
}
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
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136

（不开long long见祖宗)

线段树上二分

建树前预处理数组，将初始数组从大到小排序
建树时存储区间最小值
考虑到原先数组就是有序的，所以区间最小值也是有序的
在寻找一个数时边可对比左区间的最小值
然后向下递归便能找到所需值了

线段树可持久化

有些问题需要我们访问前几个操作线段树的值，一个暴力的思想是再克隆一颗线段树，很明显，时间空间复杂度都会爆（这样的话我还不如用数组存呢）
这时就该让可持久化线段树（主席树）登场了！
如图，这是一棵线段树

我们考虑到只修改点6时，只有1到6这条路径上的点的值受到了影响
所以我们在克隆一颗线段树时，可以只克隆这条路径上的点
而对于这条克隆路径上的点，先将左右儿子都修改为原先点的左右儿子
再将下一层修改的点赋值到对应的儿子上
如图，先克隆一个点6

回溯到点3时，克隆一个点3，左儿子为克隆的点6，右儿子仍为点7

回溯到点3时，克隆一个点1，右儿子为克隆的点3，右儿子仍为点2

于是乎我们就得到了一颗可持久化线段树
每当我们需要查找一个时间节点的线段树上的点时，我们只需要从其对应的根节点向下遍历，能保证树的结构与原先的树完全一致，时间复杂度O(logn)
P3919 【模板】可持久化线段树 1（可持久化数组）

模板（勿抄）

#include<bits/stdc++.h>
using namespace std;
const int Max=3e7;
int a[Max],root[Max],tot;
int n,m,mode,rt,value,loc;
struct node{
	int l,r,val;
}p[Max];
int build(int l,int r)
{
	int now=++tot;
	if(l==r)
	{
		p[now].val=a[l];
		return now;
	}
	int mid=(l+r)>>1;
	p[now].l=build(l,mid);
	p[now].r=build(mid+1,r);
	return now;
}
int update(int now,int l,int r,int loc,int val)
{
	++tot;
	p[tot]=p[now];
	now=tot;
	if(l==r)
	{
		p[now].val=val;
		return now;
	}
	int mid=(l+r)>>1;
	if(loc<=mid)
		p[now].l=update(p[now].l,l,mid,loc,val);
	else
		p[now].r=update(p[now].r,mid+1,r,loc,val);
	return now;
}
int Find(int now,int l,int r,int loc)
{
	if(l==r)
		return p[now].val;
	int mid=(l+r)>>1;
	if(loc<=mid)
		return Find(p[now].l,l,mid,loc);
	else
		return Find(p[now].r,mid+1,r,loc);
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	root[0]=1;
	build(1,n);
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d%d",&rt,&mode,&loc);
		if(mode==1)
		{
			scanf("%d",&value);
			root[i]=update(root[rt],1,n,loc,value);
		}
		else
		{
			printf("%d\n",Find(root[rt],1,n,loc));
			root[i]=root[rt];
		}
	}
} 
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

线段树上区间合并

我们考虑到线段树整体上是将一个大区间拆分成许多个小区间，在往上pushup时合并左右区间
我们是否能够凭此进行区间合并呢？
答案是肯定的
P5069 [Ynoi2015] 纵使日薄西山
题意概括：给出一个序列a，每次找到其中的最大值并将其和其左右的值减去1，若为零则不再减1，问总共需要操作几次

思考一下，本质上而言对于减去一个最大的数，只有其左右的数受影响，且左右的数不会变得更大，所以可将则一整个大序列分为一个个小序列，记录不同情况时它们的所需操作次数，再分类讨论根据不同情况间的组合，结合出整个区间的答案，逐层向上合并即可
lch大佬的代码 Orz（虽然有些难看懂）

//在太阳西斜的这个世界里，置身天上之森。等这场战争结束之后，不归之人与望眼欲穿的众人， 人人本着正义之名，长存不灭的过去、逐渐消逝的未来。
//我回来了，纵使日薄西山，即便看不到未来，此时此刻的光辉，盼君勿忘。————世界上最幸福的女孩
#include<iostream>
using namespace std;
const int maxn=1e5+5;
int n,q;
int a[maxn];
struct node{
	long long t[3][3];//第一维代表左端点是否考虑，第二位代表右端点是否考虑下的答案(考虑代表该点不能删掉，即值要考虑）
	bool choose[3][3][3];//第一维代表该区间左端点是否考虑，第二维代表右端点是否考虑，第三维代表是左端点还是右端点，值为第三维是否选了
	int l;
	int r;
}tr[maxn*4];
void pushup(int o){
	int ls=o<<1,rs=o<<1|1;
	if(tr[ls].choose[1][1][1]&&tr[rs].choose[1][1][0]){//左区间的右边和右区间的左边都选
		if(a[tr[ls].r]>=a[tr[rs].l]){//左区间的右边大于右区间的左边 
			tr[o].choose[1][1][0]=tr[ls].choose[1][1][0],//整个区间的左端点等于左区间的左端点 
			tr[o].choose[1][1][1]=tr[rs].choose[0][1][1];//整个区间的右端点等于右区间不考虑左端点的情况下的右端点 
			tr[o].t[1][1]=tr[ls].t[1][1]+tr[rs].t[0][1];//整个区间的答案等于左边区间考虑左右端点的答案加上右区间不考虑左端点，考虑右端点的情况下的答案 
		}else{//左区间的右边小于右区间的左边 
			tr[o].choose[1][1][0]=tr[ls].choose[1][0][0],//整个区间的左端点等于左区间不考虑右端点的情况下的选择 
			tr[o].choose[1][1][1]=tr[rs].choose[1][1][1];//整个区间的右端点等于右区间考虑左端点，右端点的情况下的选择 
			tr[o].t[1][1]=tr[ls].t[1][0]+tr[rs].t[1][1];//整个区间的答案等于左边区间考虑左端点，不考虑右端点的答案加上右边区间考虑左右端点的情况下的答案 
		}
	}else{//左区间的右端点和右区间的左端点两者有一个不选 
		tr[o].choose[1][1][0]=tr[ls].choose[1][1][0],//整个区间的左端点是否选，取决于左区间的左端点是否选 
		tr[o].choose[1][1][1]=tr[rs].choose[1][1][1],//整个区间的右端点是否选，取决于右区间的右端点是否选 
		tr[o].t[1][1]=tr[ls].t[1][1]+tr[rs].t[1][1];//虽然没选，但是都考虑（在不选的情况下，考虑是正确的） 
	}
	if(tr[ls].choose[0][1][1]&&tr[rs].choose[1][1][0]){//左区间不考虑左端点，选择右端点并且右区间考虑左右端点并且选择左端点的情况 
		if(a[tr[ls].r]>=a[tr[rs].l]){//左区间的右端点大于右区间的左端点 
			//此处因为左区间的左端点不考虑，所以不用合并左端点 
			tr[o].choose[0][1][1]=tr[rs].choose[0][1][1];//同上合并右端点（因为右区间的左端点值小于左区间的右端点值，所以后面就不用考虑右区间的左端点) 
			tr[o].t[0][1]=tr[ls].t[0][1]+tr[rs].t[0][1];//合并答案 
		}else{
			tr[o].choose[0][1][1]=tr[rs].choose[1][1][1];//同上(右区间此时左右端点都考虑左区间的左右端点都不考虑） 
			tr[o].t[0][1]=tr[ls].t[0][0]+tr[rs].t[1][1];//合并答案 
		}
	}else{
		tr[o].choose[0][1][1]=tr[rs].choose[1][1][1],//直接合并(因为左区间的左端点不考虑，所以整个区间的左端点也不用考虑) 
		tr[o].t[0][1]=tr[ls].t[0][1]+tr[rs].t[1][1];//合并答案 
	}
	if(tr[ls].choose[1][1][1]&&tr[rs].choose[1][0][0]){//左区间左右端点都考虑，选右端点，右区间只考虑左端点，选左端点 
		if(a[tr[ls].r]>=a[tr[rs].l]){//同上 
			tr[o].choose[1][0][0]=tr[ls].choose[1][1][0];//整个区间的左端点考虑，右端点不考虑 
			tr[o].t[1][0]=tr[ls].t[1][1]+tr[rs].t[0][0];//合并答案 
		}else{
			tr[o].choose[1][0][0]=tr[ls].choose[1][0][0];//懒得解释了 
			tr[o].t[1][0]=tr[ls].t[1][0]+tr[rs].t[1][0];//合并答案 
		}
	}else{
		tr[o].choose[1][0][0]=tr[ls].choose[1][1][0],//左选右不选 
		tr[o].t[1][0]=tr[ls].t[1][1]+tr[rs].t[1][0];//合并答案 
	}
	if(tr[ls].choose[0][1][1]&&tr[rs].choose[1][0][0]){//懒得解释 * 2 剩下的自己看吧..... 
		if(a[tr[ls].r] >= a[tr[ls].r + 1]){
			tr[o].t[0][0]=tr[ls].t[0][1]+tr[rs].t[0][0];
		}else{
			tr[o].t[0][0]=tr[ls].t[0][0]+tr[rs].t[1][0];
		}
	}else{
		tr[o].t[0][0]=tr[ls].t[0][1]+tr[rs].t[1][0];
	}
}
void build(int o,int l,int r){
	tr[o].l=l,tr[o].r=r;
	if(l==r){
		tr[o].t[1][1]=a[l];
		tr[o].choose[1][1][0]=1,tr[o].choose[1][1][1]=1;//左右端点都考虑，选左 = true，选右 = true； 
		tr[o].choose[1][0][0]=0,tr[o].choose[1][0][1]=0;
		tr[o].choose[0][1][0]=0,tr[o].choose[0][1][1]=0;
		return;
	}
	int ls=o<<1,rs=o<<1|1,mid=(l+r)>>1;
	build(ls,l,mid);
	build(rs,mid+1,r);
	pushup(o);
}
void update(int o,int l,int r,int x,int y){
	if(l==r){
		a[x]=y;
		tr[o].t[1][1]=y;
		return;
	}
	int ls=o<<1,rs=o<<1|1,mid=(l+r)>>1;
	if(x<=mid)update(ls,l,mid,x,y);
	else update(rs,mid+1,r,x,y);
	pushup(o);
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	build(1,1,n);
	cin>>q;
	int x,y;
	while(q--){
		cin>>x>>y;
		update(1,1,n,x,y);
		cout<<tr[1].t[1][1]<<endl;
	}
	return 0;
}
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

线段树合并

原题：雨天的尾巴
（其实这道题还有一个树剖写法，但我懒得写了）
显而易见的是，我们的目标就是在x到y的路径上，对每个点都加上一个z，同时维护他们的数量最大值和编号
一个很暴力的思想就是在这条路径上的每个点都开一个数组，，每次存储下它的值
毫无疑问，肯定会爆（时间和空间两个层面上的）
再想想，由于我们只需要在最后一刻统计出他们的最大值，所以我们可以使用树上差分，来存储他们加上的z
最后自下而上合并即可
还是会爆（时间上的）
我们发现，现在的复杂度瓶颈在于找最大值上
所以我们考虑对每一个点开一棵线段树，维护一个区间中的数量最多的编号最小值
纳尼？？？？？？？？你怕不是疯了？？？？？？
对每个点都开一颗线段树，空间不会爆吗？
答：不会，我们使用动态开点线段树维护
两颗线段树合并的话，不就相当于建了棵线段树吗，时间不爆？
答：这就是线段树合并出场的时机了
我们对两棵线段树进行合并，规定将b的值合并到a
如果a的左儿子为空，则再怎么遍历答案都是b的值
那我们就将a的左儿子设为b的左儿子
a的右儿子同理
如果b的左儿子为空，则再怎么遍历都没用，则a的左儿子继续保持，结束递归
右儿子同理
可以证明时间复杂度为O(两颗线段树的交)
最坏情况下为O(nlogn)
就完美解决这个问题啦

#include<bits/stdc++.h>
using namespace std;
const int Max=3e6+5;
struct edge{
	int to,next;
}p[Max];
int head[Max],last[Max],dep[Max],fa[Max][25],idx,ans[Max];
void add(int u,int v)
{
	if(head[u])
		p[last[u]].next=++idx;
	else
		head[u]=++idx;
	last[u]=idx;
	p[idx].to=v;
}
void dfs(int now,int from) 
{
	dep[now]=dep[from]+1;
	fa[now][0]=from;
	for(int i=1;i<=20;i++)
	{
		fa[now][i]=fa[fa[now][i-1]][i-1];
	}
	for(int i=head[now];p[i].to!=0;i=p[i].next)
	{
		if(p[i].to==from)
			continue;
		dfs(p[i].to,now);
	}
}
int lca(int u,int v)
{
	if(dep[u]>dep[v])
	{
		for(int i=20;i>=0;i--)
		{
			if(dep[fa[u][i]]>dep[v])
				u=fa[u][i];
		}
		u=fa[u][0];
	}
	else if(dep[u]<dep[v])
	{
		for(int i=20;i>=0;i--)
		{
			if(dep[fa[v][i]]>dep[u])
				v=fa[v][i];
		}
		v=fa[v][0];
	}
	if(u==v)
		return u;
	for(int i=20;i>=0;i--)
	{
		if(fa[u][i]!=fa[v][i])
		{
			u=fa[u][i];
			v=fa[v][i];
		}
	}
	return fa[u][0];
}

int tot=0;
struct tree{
	int ls,rs,cnt,rank;
	tree()
	{
		rank=0;
		cnt=0;
	}
	tree(int lss,int rss,int cntt)
	{
		ls=lss;
		rs=rss;
		cnt=cntt;
		rank=0;
	}
}t[Max*4];
void pushup(int now)
{
	//t[now].cnt=max(t[t[now].ls].cnt,t[t[now].rs].cnt);
	if(t[t[now].ls].cnt>t[t[now].rs].cnt)
	{
		t[now].cnt=t[t[now].ls].cnt;
		t[now].rank=t[t[now].ls].rank;
	}
	else if(t[t[now].ls].cnt<t[t[now].rs].cnt)
	{
		t[now].cnt=t[t[now].rs].cnt;
		t[now].rank=t[t[now].rs].rank;
	}
	else
	{
		t[now].cnt=t[t[now].ls].cnt;
		t[now].rank=min(t[t[now].rs].rank,t[t[now].ls].rank);
	}
}
void update(int now,int l,int r,int loc,int num)
{
	if(l==r)
	{
		t[now].cnt+=num;
		t[now].rank=loc;
		return ;
	}
	int mid=(l+r)>>1;
	if(loc<=mid)
	{
		if(!t[now].ls)
		{
			t[now].ls=++tot;
			t[tot]=*new tree(0,0,0);
		}
		update(t[now].ls,l,mid,loc,num);	
	}
	else
	{
		if(!t[now].rs)
		{
			t[now].rs=++tot;
			t[tot]=*new tree(0,0,0);
		}
		update(t[now].rs,mid+1,r,loc,num);
	}
	pushup(now);
}

void merge(int a,int b,int l,int r)
{
	if(l==r)
	{
		t[a].cnt+=t[b].cnt;
		t[a].rank=l;
		return ;
	}
	if(t[b].ls)
	{
		if(!t[a].ls)
		{
			t[a].ls=t[b].ls;
		}
		else
			merge(t[a].ls,t[b].ls,l,(l+r)/2);
	}
	if(t[b].rs)
	{
		if(!t[a].rs)
		{
			t[a].rs=t[b].rs;
		}
		else
			merge(t[a].rs,t[b].rs,((l+r)/2)+1,r);
	}
	pushup(a);
}

void dfs2(int now,int from)
{
	for(int i=head[now];p[i].to!=0;i=p[i].next)
	{
		if(p[i].to==from)
			continue;
		dfs2(p[i].to,now);
	}
	for(int i=head[now];p[i].to!=0;i=p[i].next)
	{
		if(p[i].to==from)
			continue;
		merge(now,p[i].to,1,100000);
	}
	ans[now]=t[now].rank;
}
int main()
{
	int n,m,a,b,c;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n-1;i++)
	{
		scanf("%d%d",&a,&b);
		add(a,b);
		add(b,a);
	}
	dfs(1,1);
	fa[1][0]=0;
	tot=n;
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d%d",&a,&b,&c);
		update(a,1,100000,c,1);
		update(b,1,100000,c,1);
		int Lca=lca(a,b);
		update(Lca,1,100000,c,-1);
		update(fa[Lca][0],1,100000,c,-1);
	}
	dfs2(1,1);
	for(int i=1;i<=n;i++)
	{
		printf("%d\n",ans[i]);
	}
}
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
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202