A - 敌兵布阵
中央情报局要研究敌人究竟演习什么战术,所以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, A1, A2, ... , 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 A1, A2, ... , AN. -1000000000 ≤ Ai ≤ 1000000000.
Each of the next Q lines represents an operation.
"C a b c" means adding c to each of Aa, Aa+1, ... , Ab. -10000 ≤ c ≤ 10000.
"Q a b" means querying the sum of Aa, Aa+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("%dn", 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 }
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("%dn", 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 }
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("%I64dn", 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 }
- 还没有人评论，欢迎说说您的想法！
客服
