线段树题解(3题)

2018-06-17 21:48:58来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

A - 敌兵布阵

C国的死对头A国这段时间正在进行军事演习,所以C国间谍头子Derek和他手下Tidy又开始忙乎了。A国在海岸线沿直线布置了N个工兵营地,Derek和Tidy的任务就是要监视这些工兵营地的活动情况。由于采取了某种先进的监测手段,所以每个工兵营地的人数C国都掌握的一清二楚,每个工兵营地的人数都有可能发生变动,可能增加或减少若干人手,但这些都逃不过C国的监视。 
中央情报局要研究敌人究竟演习什么战术,所以Tidy要随时向Derek汇报某一段连续的工兵营地一共有多少人,例如Derek问:“Tidy,马上汇报第3个营地到第10个营地共有多少人!”Tidy就要马上开始计算这一段的总人数并汇报。但敌兵营地的人数经常变动,而Derek每次询问的段都不一样,所以Tidy不得不每次都一个一个营地的去数,很快就精疲力尽了,Derek对Tidy的计算速度越来越不满:"你个死肥仔,算得这么慢,我炒你鱿鱼!”Tidy想:“你自己来算算看,这可真是一项累人的工作!我恨不得你炒我鱿鱼呢!”无奈之下,Tidy只好打电话向计算机专家Windbreaker求救,Windbreaker说:“死肥仔,叫你平时做多点acm题和看多点算法书,现在尝到苦果了吧!”Tidy说:"我知错了。。。"但Windbreaker已经挂掉电话了。Tidy很苦恼,这么算他真的会崩溃的,聪明的读者,你能写个程序帮他完成这项工作吗?不过如果你的程序效率不够高的话,Tidy还是会受到Derek的责骂的. 

Input第一行一个整数T,表示有T组数据。 
每组数据第一行一个正整数N(N<=50000),表示敌人有N个工兵营地,接下来有N个正整数,第i个正整数ai代表第i个工兵营地里开始时有ai个人(1<=ai<=50)。 
接下来每行有一条命令,命令有4种形式: 
(1) Add i j,i和j为正整数,表示第i个营地增加j个人(j不超过30) 
(2)Sub i j ,i和j为正整数,表示第i个营地减少j个人(j不超过30); 
(3)Query i j ,i和j为正整数,i<=j,表示询问第i到第j个营地的总人数; 
(4)End 表示结束,这条命令在每组数据最后出现; 
每组数据最多有40000条命令 
Output对第i组数据,首先输出“Case i:”和回车, 
对于每个Query询问,输出一个整数并回车,表示询问的段中的总人数,这个数保持在int以内。 
Sample Input

1
10
1 2 3 4 5 6 7 8 9 10
Query 1 3
Add 3 6
Query 2 7
Sub 10 2
Add 6 3
Query 3 10
End 

Sample Output

Case 1:
6
33
59

B - I Hate It

很多学校流行一种比较的习惯。老师们很喜欢询问,从某某到某某当中,分数最高的是多少。 
这让很多学生很反感。 

不管你喜不喜欢,现在需要你做的是,就是按照老师的要求,写一个程序,模拟老师的询问。当然,老师有时候需要更新某位同学的成绩。

Input本题目包含多组测试,请处理到文件结束。 
在每个测试的第一行,有两个正整数 N 和 M ( 0<N<=200000,0<M<5000 ),分别代表学生的数目和操作的数目。 
学生ID编号分别从1编到N。 
第二行包含N个整数,代表这N个学生的初始成绩,其中第i个数代表ID为i的学生的成绩。 
接下来有M行。每一行有一个字符 C (只取'Q'或'U') ,和两个正整数A,B。 
当C为'Q'的时候,表示这是一条询问操作,它询问ID从A到B(包括A,B)的学生当中,成绩最高的是多少。 
当C为'U'的时候,表示这是一条更新操作,要求把ID为A的学生的成绩更改为B。 
Output对于每一次询问操作,在一行里面输出最高成绩。Sample Input

5 6
1 2 3 4 5
Q 1 5
U 3 6
Q 3 4
Q 4 5
U 2 9
Q 1 5

Sample Output

5
6
5
9

 

C - A Simple Problem with Integers

 

You have N integers, A1A2, ... , AN. You need to deal with two kinds of operations. One type of operation is to add some given number to each number in a given interval. The other is to ask for the sum of numbers in a given interval.

Input

The first line contains two numbers N and Q. 1 ≤ N,Q ≤ 100000.
The second line contains N numbers, the initial values of A1A2, ... , AN. -1000000000 ≤ Ai ≤ 1000000000.
Each of the next Q lines represents an operation.
"C a b c" means adding c to each of AaAa+1, ... , Ab. -10000 ≤ c ≤ 10000.
"Q a b" means querying the sum of AaAa+1, ... , Ab.

Output

You need to answer all Q commands in order. One answer in a line.

Sample Input

10 5
1 2 3 4 5 6 7 8 9 10
Q 4 4
Q 1 10
Q 2 4
C 3 6 3
Q 2 4

Sample Output

4
55
9
15



这3题都是线段树的模板题了,A题是点修改的求和问题,B题则是求一个区间中的最大值,C题是区间修改的求和问题。

为啥这些题要用线段树这种数据结构来存储呢?当然是为了减少时间复杂度,从A题可以看出N的最大值为50000,而执行的操作也有40000之多,如果用一般的数组来存储数据,再进行区间求和和点修改。。。
即:1. 对于简单的区间求和,我们有两种做法,1是直接将区间中的数相加,那么所需的时间复杂度为O(n),而操作次数有40000次,N的最大值为50000,那么最后肯定会超时,第二种方法则是用数组存之前所有树的和,那么每次查询
操作只需要O(1),这是不会超时的。
2. 对于定点修改,

很明显两种方法都会超时。而线段树的时间复杂度只有log2(R-L+1)。

线段树用的存储结构是二叉树,但每一个节点中存的东西都是你所要求的东西。

对于线段树来说,最先要实现的就是Build()函数,即建树。

接着便是PushUp()函数,PushUp()函数的作用是修改你所修改区间的父区间的值,而PushDown()恰恰相反,PushDown()是修改你所修改区间的子区间的值,但实现PushDown()

的作用需要一个懒惰标记,即但你递归到被修改区间的子区间时,则会将标记下推,同时修改子区间的值。

然后便是Update()函数,即修改函数。最后用Query()函数得出答案即可。

由于都是模板题,就直接贴码了。

 

如果对于线段树没有什么了解的可以去这里了解一下:http://blog.csdn.net/zearot/article/details/48299459

 

A题:

 1 #include <stdio.h>
 2 
 3 #define max 50002
 4 
 5 int p[max], n;
 6 int m[max<<2];
 7 
 8 void PushUp(int rt) {
 9     m[rt] = m[rt << 1] + m[rt << 1 | 1];
10 }
11 
12 void Build(int l, int r, int rt) {
13     if (l == r) {
14         m[rt] = p[l];
15         return;
16     }
17     int j = (l + r) >> 1;
18     Build(l, j, rt << 1);
19     Build(j + 1, r, rt << 1 | 1);
20     PushUp(rt);
21 }
22 
23 void Updata(int L, int C, int l, int r, int rt) {
24     if (l == r) {
25         m[rt] += C;
26         return;
27     }
28     int j = (l + r) >> 1;
29     if (L <= j)Updata(L, C, l, j, rt << 1);
30     else Updata(L, C, j + 1, r, rt << 1 | 1);
31     PushUp(rt);
32 }
33 
34 int Query(int L, int R, int l, int r, int rt) {
35     if (L <= l&&r <= R) {
36         return m[rt];
37     }
38     int j = (l + r) >> 1;
39     int ans = 0;
40     if (L <= j)ans += Query(L, R, l, j, rt << 1);
41     if (R > j)ans += Query(L, R, j + 1, r, rt << 1 | 1);
42     return ans;
43 }
44 
45 int main()
46 {
47     int t;
48     scanf("%d", &t);
49     int count = 1;
50     while (t--) {
51         scanf("%d", &n);
52         for (int i = 1; i <= n; i++) {
53             scanf("%d", &p[i]);
54         }
55         char k[10];
56         printf("Case %d:\n", count++);
57         Build(1, n, 1);
58         while (1) {
59             scanf("%s",&k);
60             if (k[0] == 'Q') {
61                 int a, b;
62                 scanf("%d%d", &a, &b);
63                 int ans = Query(a, b, 1, n, 1);
64                 printf("%d\n", ans);
65             }
66             else if (k[0] == 'A') {
67                 int a, b;
68                 scanf("%d%d", &a, &b);
69                 Updata(a, b, 1, n, 1);
70             }
71             else if (k[0] == 'S') {
72                 int a, b;
73                 scanf("%d%d", &a, &b);
74                 Updata(a, -b, 1, n, 1);
75             }
76             else {
77                 break;
78             }
79         }
80     }
81     return 0;
82 }
View Code

B题:

 1 #include <stdio.h>
 2 #include <algorithm>
 3 using namespace std;
 4 
 5 #define Max 200002
 6 
 7 int p[Max], n, m, ans;
 8 int sum[Max << 2];
 9 
10 void PushUp(int rt) {
11     sum[rt] = max(sum[rt << 1], sum[rt << 1 | 1]);
12 }
13 
14 void Build(int l, int r, int rt) {
15     if (l == r) {
16         sum[rt] = p[l];
17         return;
18     }
19     int j = (l + r) >> 1;
20     Build(l, j, rt << 1);
21     Build(j + 1, r, rt << 1 | 1);
22     PushUp(rt);
23 }
24 
25 void Updata(int L, int C, int l, int r, int rt) {
26     if (l == r) {
27         sum[rt] = C;
28         return;
29     }
30     int j = (l + r) >> 1;
31     if (L <= j)Updata(L, C, l, j, rt << 1);
32     else Updata(L, C, j + 1, r, rt << 1 | 1);
33     PushUp(rt);
34 }
35 
36 void Query(int L, int R, int l, int r, int rt) {
37     if (L <= l&&r <= R) {
38         ans = max(ans, sum[rt]);
39         return;
40     }
41     int j = (l + r) >> 1;
42     if (L <= j) Query(L, R, l, j, rt << 1);
43     if (R > j)Query(L, R, j + 1, r, rt << 1 | 1);
44 }
45 
46 int main()
47 {
48     while (scanf("%d%d", &n, &m) != EOF) {
49         for (int i = 1; i <= n; i++) {
50             scanf("%d", &p[i]);
51         }
52         Build(1, n, 1);
53         char q[5];
54         int a, b;
55         for (int i = 1; i <= m; i++) {
56             scanf("%s", q);
57             scanf("%d%d",&a,&b);
58             if (q[0] == 'Q') {
59                 ans = 0;
60                 Query(a, b, 1, n, 1);
61                 printf("%d\n", ans);
62             }
63             else if (q[0] == 'U') {
64                 p[a] = b;
65                 Updata(a, b, 1, n, 1);
66             }
67         }
68     }
69     return 0;
70 }
View Code

C题:

 1 #include <stdio.h>
 2 #include <string.h>
 3 
 4 #define Maxn 100002
 5 
 6 long long Sum[Maxn << 2], Add[Maxn << 2];
 7 long long A[Maxn], n, m;
 8 
 9 void PushUp(int rt) {
10     Sum[rt] = Sum[rt << 1] + Sum[rt << 1 | 1];
11 }
12 
13 void PushDown(int rt,int ln,int rn) {
14     if (Add[rt]) {
15         Add[rt << 1] += Add[rt];
16         Add[rt << 1 | 1] += Add[rt];
17         Sum[rt << 1] += Add[rt] * ln;
18         Sum[rt << 1 | 1] += Add[rt] * rn;
19         Add[rt] = 0;
20     }
21 }
22 
23 void Build(int l, int r, int rt) {
24     if (l == r) {
25         Sum[rt] = A[l];
26         return;
27     }
28     int j = (l + r) >> 1;
29     Build(l, j, rt << 1);
30     Build(j + 1, r, rt << 1 | 1);
31     PushUp(rt);
32 }
33 
34 /*void Updata(int R, int C, int l, int r, int rt) {
35     if (l == r) {
36         Sum[rt] += C;
37         return;
38     }
39     int j = (l + r) >> 1;
40     PushDown(rt, j - l + 1, r - m);
41     if (R <= j)Updata(R, C, l, j, rt << 1);
42     else Updata(R, C, j + 1, r, rt << 1 | 1);
43     PushUp(rt);
44 }*/
45 
46 void Updata(int L, int R, int C, int l, int r, int rt) {
47     if (L <= l&&r <= R) {
48         Sum[rt] += (r - l + 1)*C;
49         Add[rt] += C;
50         return;
51     }
52     int j = (l + r) >> 1;
53     PushDown(rt, j - l + 1, r - j);
54     if (L <= j)Updata(L, R, C, l, j, rt<<1);
55     if (R > j)Updata(L, R, C, j + 1, r, rt << 1 | 1);
56     PushUp(rt);
57 }
58 
59 long long Query(int L, int R, int l, int r, int rt) {
60     if (L <= l&&r <= R) {
61         return Sum[rt];
62     }
63     int j = (l + r) >> 1;
64     PushDown(rt, j - l + 1, r - j);
65     long long ans = 0;
66     if (L <= j)ans += Query(L, R, l, j, rt << 1);
67     if (R > j)ans += Query(L, R, j + 1, r, rt << 1 | 1);
68     return ans;
69 }
70 
71 int main()
72 {
73     while (scanf("%lld%lld", &n, &m) != EOF) {
74         for (int i = 1; i <= n; i++) {
75             scanf("%lld", &A[i]);
76         }
77         memset(Add, 0, sizeof(Add));
78         Build(1, n, 1);
79         char p[5];
80         for (int i = 1; i <= m; i++) {
81             scanf("%s", p);
82             if (p[0] == 'Q') {
83                 int a, b;
84                 scanf("%d%d", &a, &b);
85                 printf("%I64d\n", Query(a, b, 1, n, 1));
86             }
87             else {
88                 int a, b, c;
89                 scanf("%d%d%d", &a, &b, &c);
90                 Updata(a, b, c, 1, n, 1);
91             }
92         }
93     }
94     return 0;
95 }
View Code

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:HDU_5532_Almost Sorted Array

下一篇:hihoCoder_1449_后缀自动机三&#183;重复旋律6