呓语 | 杨英明的个人博客

专注于c++、Python,欢迎交流

By

蓝桥杯 算法训练 操作格子(线段树,点更新)

算法训练 操作格子  

时间限制:1.0s   内存限制:256.0MB
      
问题描述

有n个格子,从左到右放成一排,编号为1-n。

共有m次操作,有3种操作类型:

1.修改一个格子的权值,

2.求连续一段格子权值和,

3.求连续一段格子的最大值。

对于每个2、3操作输出你所求出的结果。

输入格式

第一行2个整数n,m。

接下来一行n个整数表示n个格子的初始权值。

接下来m行,每行3个整数p,x,y,p表示操作类型,p=1时表示修改格子x的权值为y,p=2时表示求区间[x,y]内格子权值和,p=3时表示求区间[x,y]内格子最大的权值。

输出格式

有若干行,行数等于p=2或3的操作总数。

每行1个整数,对应了每个p=2或3操作的结果。

样例输入
4 3
1 2 3 4
2 1 3
1 4 3
3 1 4
样例输出
6
3
数据规模与约定

对于20%的数据n <= 100,m <= 200。

对于50%的数据n <= 5000,m <= 5000。

对于100%的数据1 <= n <= 100000,m <= 100000,0 <= 格子权值 <= 10000。


 
  线段树,点更新
  线段树每一个节点代表一个区间,并存储有这个区间的特定值,例如这个区间最大值,区间和等等……而这道题的特定值有两个,权值和 和 最大权值。
  思路
  没有什么特殊的地方,按照正常的线段树的思路来做即可。
  * 每个节点存储权值和val,最大权值mx;
  1.更新的时候,递归找到底,val和mx一起修改,然后一层层的返回的时候,用Push_up(),不断更新val和mx;
  2.查询权值和的时候,递归往下找,直到找到要查询的区间为止,返回该区间节点的权值和val;
  3.查询最大权值的时候,也是递归向下找,找到查询区间之后,返回节点的最大权值mx。
  以上就为基本的步骤了,另外注意Push_up()的编写。
  写这道题的时候,线段树用的还不是很熟,第一遍写完之后,测试数据不对,又修改了很多地方才通过。所以做线段树的题,要注意好细节。总的来说,这道题是一道不错的线段树的练手题。
  代码
  1 #include <iostream>
  2 #include <stdio.h>
  3 using namespace std;
  4 #define MAXN 100010
  5 struct Node{
  6     int left,right;
  7     int val,mx; //权值和最大值
  8 };
  9 Node tree[MAXN*3+1];
 10 int Max(int a,int b)    //返回两数较大值
 11 {
 12     return a>b?a:b;
 13 }
 14 void Push_up(int d)
 15 {
 16     tree[d].val = tree[d<<1].val + tree[d<<1|1].val;
 17     tree[d].mx = Max(tree[d<<1].mx , tree[d<<1|1].mx);
 18 }
 19 void Init(int d,int l,int r)    //初始化线段树
 20 {
 21     if(l==r){
 22         tree[d].left = l;
 23         tree[d].right = r;
 24         scanf("%d",&tree[d].val);   //读取数据
 25         tree[d].mx = tree[d].val;
 26         return ;
 27     }
 28 
 29     int mid = (l+r)/2;
 30     tree[d].left = l;
 31     tree[d].right = r;
 32     Init(d<<1,l,mid);
 33     Init(d<<1|1,mid+1,r);
 34     Push_up(d);
 35 }
 36 void Update(int d,int l,int r,int x)  //1.修改一个格子的权值。[l,r]为要找的区间,在这道题里l==r。x为要修改的值
 37 {
 38     if(tree[d].left==l && tree[d].right==r){    //找到区间。
 39         tree[d].val = x;
 40         tree[d].mx = x;
 41         return ;
 42     }
 43     if(tree[d].left == tree[d].right){  //没找到区间
 44         return ;
 45     }
 46 
 47     int mid = (tree[d].left+tree[d].right)/2;
 48     if(mid>=r){ //去左区间
 49         Update(d<<1,l,r,x);
 50     }
 51     else if(mid<l){ //去右区间
 52         Update(d<<1|1,l,r,x);
 53     }
 54     else {  //mid在中间
 55         Update(d<<1,l,mid,x);
 56         Update(d<<1|1,mid+1,r,x);
 57     }
 58     Push_up(d);
 59 }
 60 int Query_sum(int d,int l,int r)    //2.求连续一段格子权值和
 61 {
 62     if(tree[d].left==l && tree[d].right==r){    //找到区间
 63         return tree[d].val;
 64     }
 65     if(tree[d].left==tree[d].right){    //没找到
 66         return 0;
 67     }
 68 
 69     int mid = (tree[d].left+tree[d].right)/2;
 70     if(mid>=r){
 71         return Query_sum(d<<1,l,r);
 72     }
 73     else if(mid<l){
 74         return Query_sum(d<<1|1,l,r);
 75     }
 76     else{
 77         return Query_sum(d<<1,l,mid) + Query_sum(d<<1|1,mid+1,r);
 78     }
 79 }
 80 int Query_max(int d,int l,int r)    //3.求连续一段格子的最大值
 81 {
 82     if(tree[d].left==l && tree[d].right==r){    //找到区间
 83         return tree[d].mx;
 84     }
 85     if(tree[d].left==tree[d].right){    //没找到
 86         return 0;
 87     }
 88 
 89     int mid = (tree[d].left+tree[d].right)/2;
 90     if(mid>=r){
 91         return Query_max(d<<1,l,r);
 92     }
 93     else if(mid<l){
 94         return Query_max(d<<1|1,l,r);
 95     }
 96     else{
 97         return Max(Query_max(d<<1,l,mid),Query_max(d<<1|1,mid+1,r));
 98     }
 99 }
100 int main()
101 {
102     int n,m,q,x,y;
103     while(scanf("%d%d",&n,&m)!=EOF){
104         Init(1,1,n);    //初始化
105         while(m--){
106             scanf("%d%d%d",&q,&x,&y);
107             switch(q){
108                 case 1:
109                     Update(1,x,x,y);
110                     break;
111                 case 2:
112                     printf("%d\n",Query_sum(1,x,y));
113                     break;
114                 case 3:
115                     printf("%d\n",Query_max(1,x,y));
116                     break;
117                 default:break;
118             }
119         }
120     }
121     return 0;
122 }

 

Freecode : www.cnblogs.com/yym2013

##原创声明 **转载请注明:[呓语](http://www.yangyingming.com) » [蓝桥杯 算法训练 操作格子(线段树,点更新)](http://www.yangyingming.com/article/98)**