首页 > 代码库 > 算法训练 操作格子 线段树板子题
算法训练 操作格子 线段树板子题
问题描述
有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
1 2 3 4
2 1 3
1 4 3
3 1 4
样例输出
6
3
3
数据规模与约定
对于20%的数据n <= 100，m <= 200。
对于50%的数据n <= 5000，m <= 5000。
对于100%的数据1 <= n <= 100000，m <= 100000，0 <= 格子权值 <= 10000。
1 #include<bits/stdc++.h> 2 #include<iostream> 3 #include<cstring> 4 #include<cstdio> 5 #include<algorithm> 6 #include<vector> 7 #define ll __int64 8 #define PI acos(-1.0) 9 #define mod 1000000007 10 using namespace std; 11 int n,m; 12 struct node 13 { 14 int l,r; 15 int value; 16 int maxn; 17 }tree[400005]; 18 int exm; 19 void buildtree(int root ,int l,int r) 20 { 21 tree[root].l=l; 22 tree[root].r=r; 23 if(l==r) 24 { 25 scanf("%d",&exm); 26 tree[root].value=http://www.mamicode.com/tree[root].maxn=exm; 27 return; 28 } 29 int mid=(l+r)>>1; 30 buildtree(root<<1,l,mid); 31 buildtree(root<<1|1,mid+1,r); 32 tree[root].maxn=max(tree[root<<1].maxn,tree[root<<1|1].maxn); 33 tree[root].value=http://www.mamicode.com/tree[root<<1].value+tree[root<<1|1].value; 34 } 35 void update(int root ,int what,int c) 36 { 37 if(tree[root].l==tree[root].r&&tree[root].r==what) 38 { 39 tree[root].maxn=tree[root].value=http://www.mamicode.com/c; 40 return; 41 } 42 int mid=(tree[root].l+tree[root].r)>>1; 43 if(what<=mid) 44 update(root<<1,what,c); 45 else 46 update(root<<1|1,what,c); 47 tree[root].maxn=max(tree[root<<1].maxn,tree[root<<1|1].maxn); 48 tree[root].value=http://www.mamicode.com/tree[root<<1].value+tree[root<<1|1].value; 49 } 50 int query1(int root,int l,int r) 51 { 52 if(tree[root].l==l&&tree[root].r==r) 53 { 54 return tree[root].value; 55 } 56 int mid=(tree[root].l+tree[root].r)>>1; 57 if(r<=mid) 58 return query1(root<<1,l,r); 59 else 60 { 61 if(l>mid) 62 return query1(root<<1|1,l,r); 63 else 64 return query1(root<<1,l,mid)+query1(root<<1|1,mid+1,r); 65 } 66 } 67 int query2(int root,int l,int r) 68 { 69 if(tree[root].l==l&&tree[root].r==r) 70 { 71 return tree[root].maxn; 72 } 73 int mid=(tree[root].l+tree[root].r)>>1; 74 if(r<=mid) 75 return query2(root<<1,l,r); 76 else 77 { 78 if(l>mid) 79 return query2(root<<1|1,l,r); 80 else 81 return max(query2(root<<1,l,mid),query2(root<<1|1,mid+1,r)); 82 } 83 } 84 int main() 85 { 86 int q,w,e; 87 scanf("%d %d",&n,&m); 88 buildtree(1,1,n); 89 for(int i=1;i<=m;i++) 90 { 91 scanf("%d %d %d",&q,&w,&e); 92 if(q==1) 93 update(1,w,e); 94 if(q==2) 95 printf("%d\n",query1(1,w,e)); 96 if(q==3) 97 printf("%d\n",query2(1,w,e)); 98 } 99 return 0;100 }
算法训练 操作格子 线段树板子题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。