线段树.
主要运算:
离散化(可选,当输入数据很大时有用)
建树
插入线段
统计
入门:
http://hi.baidu.com/alpc62/blog/item/469edeca0043e382c8176875.html
题目1:所有的数不大于30000的范围内讨论一个问题：现在已知n条线段，把端点依次输入告诉你，然后有m个询问，每个询问输入一个点，要求这个点在多少条线段上出现过；
代码
1
#include <stdio.h>
2#include <assert.h>
3
4//在自然数，且所有的数不大于30000的范围内讨论一个问题：现在已知n条线段，把端点依次输入告诉你，
5//然后有m个询问，每个询问输入一个点，要求这个点在多少条线段上出现过；
6
7#define MAX_NUM_PT 1000
8#define MAX_TREE_SIZE (MAX_NUM_PT*(MAX_NUM_PT+1)/2)
9
10struct line
11
{
12
int left,right;//左端点、右端点
13 int n;//记录这条线段出现了多少次，默认为0, 每个结点的左右儿子位置为2n,2n+1
14
}a[MAX_TREE_SIZE];
15
16
17void buildTree(int s,int t, int k) //要插入的线段的左端点和右端点,插入位置
18{
19 a[k].left = s;
20 a[k].right = t;
21 a[k].n = 0;
22
23 assert(k<=MAX_TREE_SIZE);
24
25 if(t>s)
26
{
27 int mid = (s+t)/2;
28
29 buildTree(s, mid, 2*k+1);
30 buildTree(mid+1, t, 2*k+2);
31
}
32}
33
34void insert(int s,int t,int step)//要插入的线段的左端点和右端点、插入位置
35{
36 if (s==a[step].left && t==a[step].right)
37 {
38 a[step].n++;//插入的线段匹配则此条线段的记录+1
39 return;//插入结束返回
40 }
41 if (a[step].left==a[step].right) return;//当前线段树的线段没有儿子，插入结束返回
42 int mid=(a[step].left+a[step].right)/2;
43 if (mid>=t) insert(s,t,step*2+1);//如果中点在t的右边，则应该插入到左儿子
44 else if (mid<s) insert(s,t,step*2+2);//如果中点在s的左边，则应该插入到右儿子
45 else//否则，中点一定在s和t之间，把待插线段分成两半分别插到左右儿子里面
46 {
47 insert(s,mid,step*2+1);
48 insert(mid+1,t,step*2+2);
49 }
50}
51
52int FindN(int pt, int k) //查询数据pt, 位置k
53{
54 int num = a[k].n;
55
56 assert (pt>=a[k].left && pt<=a[k].right);
57
58 if (a[k].left<a[k].right)
59 {
60 assert(a[k*2+1].right<a[k*2+2].left);
61
62 if(pt<=a[k*2+1].right)
63 num += FindN(pt, k*2+1);
64
65 else if(pt>=a[k*2+1].left)
66 num += FindN(pt, k*2+2);
67 }
68
69 return num;
70}
71void main()
72{
73 buildTree(0,4,0); //根节点区间为[0,4]
74 insert(1,3,0); //插入线段[1,3]
75 insert(2,3,0);
76 insert(2,4,0);
77
78 //统计每个节点的线段覆盖数目
79 for (int n=0; n<=4;n++)
80 {
81 printf("Point %d, num %d\n",n,FindN(n,0));
82 }
83}
#include <stdio.h>2
#include <assert.h>3
4
//在自然数，且所有的数不大于30000的范围内讨论一个问题：现在已知n条线段，把端点依次输入告诉你，5
//然后有m个询问，每个询问输入一个点，要求这个点在多少条线段上出现过；6
7
#define MAX_NUM_PT 10008
#define MAX_TREE_SIZE (MAX_NUM_PT*(MAX_NUM_PT+1)/2)9
10
struct line11
{
12
int left,right;//左端点、右端点13
int n;//记录这条线段出现了多少次，默认为0, 每个结点的左右儿子位置为2n,2n+114
}a[MAX_TREE_SIZE];15
16
17
void buildTree(int s,int t, int k) //要插入的线段的左端点和右端点,插入位置18
{19
a[k].left = s;20
a[k].right = t;21
a[k].n = 0;22
23
assert(k<=MAX_TREE_SIZE);24
25
if(t>s)26
{
27
int mid = (s+t)/2;28
29
buildTree(s, mid, 2*k+1);30
buildTree(mid+1, t, 2*k+2);31
}32
}33
34
void insert(int s,int t,int step)//要插入的线段的左端点和右端点、插入位置35
{36
if (s==a[step].left && t==a[step].right)37
{38
a[step].n++;//插入的线段匹配则此条线段的记录+139
return;//插入结束返回40
}41
if (a[step].left==a[step].right) return;//当前线段树的线段没有儿子，插入结束返回42
int mid=(a[step].left+a[step].right)/2;43
if (mid>=t) insert(s,t,step*2+1);//如果中点在t的右边，则应该插入到左儿子44
else if (mid<s) insert(s,t,step*2+2);//如果中点在s的左边，则应该插入到右儿子45
else//否则，中点一定在s和t之间，把待插线段分成两半分别插到左右儿子里面46
{47
insert(s,mid,step*2+1);48
insert(mid+1,t,step*2+2);49
}50
}51
52
int FindN(int pt, int k) //查询数据pt, 位置k53
{54
int num = a[k].n;55
56
assert (pt>=a[k].left && pt<=a[k].right);57
58
if (a[k].left<a[k].right)59
{60
assert(a[k*2+1].right<a[k*2+2].left);61
62
if(pt<=a[k*2+1].right)63
num += FindN(pt, k*2+1);64
65
else if(pt>=a[k*2+1].left)66
num += FindN(pt, k*2+2);67
}68
69
return num;70
}71
void main()72
{73
buildTree(0,4,0); //根节点区间为[0,4]74
insert(1,3,0); //插入线段[1,3]75
insert(2,3,0); 76
insert(2,4,0);77
78
//统计每个节点的线段覆盖数目79
for (int n=0; n<=4;n++)80
{81
printf("Point %d, num %d\n",n,FindN(n,0));82
}83
}
- 上一篇 Fft算法.
- 下一篇 最长公共子序列, 最长递增子序列.