战功统计 1
时间限制： 2 秒 内存限制： 128M
题目描述
小可将军统率着n个士兵，士兵分别编号为1~n。已知他们现在的战功 a[i]，要为他们统计接下来的战功，战功可以透支使用，即战功可能为负数
杀敌可以增加战功，且战功可以兑换物资，所有战功会有增有减，统称为战功的变化
将军经常爱拿某一段编号内战功最高的人与战功最低的人进行比较，计算出两个人的战功差值，以鼓舞战士们奋勇杀敌。所以，将军经常问军师小工第 i 号士兵到第 j 号士兵中，战功最高的人与战功最低的人的战功差值是多少
故而一共有两种战功操作：
1 x y：表示 x 号战士的战功增加 y
2 L R：表示查询 L 到 R 战士的最高战功和最低战功的差值
输入描述
第一行：输入 n m，分别表示 n 个战士，m 次战功操作
第二行：输入 n 个数表示每个人现在的战功
接下来m行：每行输入3个数，表示一次战功操作
输出描述
对于每次查询，输出 L 到 R 战士的最高战功和最低战功的差值
输入样例
3 2
1 2 3
1 2 10
2 1 3
输出样例
11
本题思路：
本题目相比模板而讲，不同之处在这里：
2 L R：表示查询 L 到 R 战士的最高战功和最低战功的差值
在模板中，是求区间和，而在本题目是要求最大值-最小值。
所以，我们在结构体中要加入ma和mi变量，分别是最大值和最小值，与模版相比，本题无需求和，不需要value变量和ans求值。
在存取当前点root的值时，同时存取ma和mi。
在query求最大值和最小值的时候，需要使用STL中的pair<long long,long long>来一次存储2个数，first存储最大值，second存储最小值。
提示：线段树是什么？去Goodnotes中找寻曾经的笔记吧！（笔记本名称：算法笔记本）
1: #include<bits/stdc++.h>
2: #define ll long long
3: #define N 1001
4: using namespace std;
5: int n,m;
6: struct node{
7: int value/*该节点的值*/,left,right/*区间左右端*/;
8: }tree[N];
9: void build(int root,int l,int r){
10: tree[root].left=l;
11: tree[root].right=r;
12: if(tree[root].left==tree[root].right){//当找到l和r相等的节点，如[2,2]赋值
13: tree[root].value=a[l];//l或r都可以
14: return;
15: }
16: int mid=(l+r)/2;//二分找儿子
17: build(root*2,l,mid);//左孩子
18: build(root*2+1,mid+1,r);//有孩子
19: tree[root].value=tree[2*root].value+tree[2*root+1].value;//将儿子的值加到父亲上
20: }
21: int query(int root,int l,int r){//查询某个区间和
22: if(l<=tree[root].left&&tree[root].right>=r){//当前查询的区间完全包含当前节点的区间时
23: return tree[root].value;
24: }
25: int mid=(tree[root].left+tree[root].right)/2;
26: int ans=0;//累加变量ans
27: if(l<=mid){//如果当前节点的左子树包含一部分查询内容
28: ans+=query(2*root,l,r);
29: }
30: if(r>mid){//如果当前节点的右子树包含一部分查询内容
31: ans+=query(2*root,l,r);
32: }
33: }
34: void update(int root,int n,int v){//n是要更改的点，v是要改成的值
35: if(tree[root].left==tree[root].right){//当某一点的left和right相等时，更新该节点
36: tree[root].value=v;
37: return;
38: }
39: int mid=(tree[root].left+tree[root].right)/2;
40: if(n<=mid){//二分找儿子
41: update(2*root,n,v);
42: }
43: else{
44: update(2*root+1,n,v);
45: }
46: tree[root].value=tree[2*root].value+tree[2*root+1].value;
47: }
48:
49: int main(){
50:
51: return 0;
52: }
本题AC代码：
1. #include<bits/stdc++.h>
2. #define ll long long
3. #define N 1000001
4. #define pa pair<long long,long long>
5. using namespace std;
6. int n,m,a[4*N];
7. struct node{
8. ll ma,mi;
9. int left,right;
10. }tree[4*N];
11. void build(int root,int l,int r){
12. tree[root].left=l;
13. tree[root].right=r;
14. if(tree[root].left==tree[root].right){
15. tree[root].ma=a[l];
16. tree[root].mi=a[l];
17. return;
18. }
19. int mid=(l+r)/2;
20. build(root*2,l,mid);
21. build(root*2+1,mid+1,r);
22. tree[root].ma=max(tree[2*root].ma,tree[2*root+1].ma);
23. tree[root].mi=min(tree[2*root].mi,tree[2*root+1].mi);
24. }
25. pa query(int root,int l,int r){
26. if(l<=tree[root].left&&r>=tree[root].right){
27. return {tree[root].ma,tree[root].mi};
28. }
29. ll maxx=-0x3f3f3f3f,minn=0x3f3f3f3f;
30. int mid=(tree[root].left+tree[root].right)/2;
31. if(l<=mid){
32. pa pi=query(2*root,l,r);
33. maxx=max(maxx,pi.first);
34. minn=min(minn,pi.second);
35. }
36. if(r>mid){
37. pa pi=query(2*root+1,l,r);
38. maxx=max(maxx,pi.first);
39. minn=min(minn,pi.second);
40. }
41. return {maxx,minn};
42. }
43. void update(int root,int n,int v){
44. if(tree[root].left==tree[root].right){
45. tree[root].ma+=v;
46. tree[root].mi+=v;
47. return;
48. }
49. int mid=(tree[root].left+tree[root].right)/2;
50. if(n<=mid){
51. update(2*root,n,v);
52. }
53. else{
54. update(2*root+1,n,v);
55. }
56. tree[root].ma=max(tree[2*root].ma,tree[2*root+1].ma);
57. tree[root].mi=min(tree[2*root].mi,tree[2*root+1].mi);
58. }
59. int main(){
60. scanf("%d%d",&n,&m);
61. for(int i=1;i<=n;i++){
62. scanf("%d",&a[i]);
63. }
64. build(1,1,n);
65. for(int i=1;i<=m;i++){
66. int t,x,y;
67. scanf("%d%d%d",&t,&x,&y);
68. if(t==1){
69. update(1,x,y);
70. }else{
71. pa pi=query(1,x,y);
72. printf("%lld\n",pi.first-pi.second);
73. }
74. }
75. return 0;
76. }
