算法训练操作格子

2019-11-06 07:01:14

字体：大中小

来源：转载

供稿：网友

算法训练操作格子时间限制：1.0s 内存限制：256.0MB 提交此题锦囊1 锦囊2 问题描述有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。

线段树，更新用位运算

#include<cstdio>#include <iostream>using namespace std;int sum,n,maxn;struct node{ int l,r,n,sum;} a[1000000];void init(int l,int r,int i){ a[i].l = l; a[i].r = r; a[i].n = 0; a[i].sum = 0; if(l!=r) { int mid = (l+r)/2; init(l,mid,i<<1); init(mid+1,r,i<<1|1); }}void insert(int i,int x,int m){ if(x>=a[i].l && x<=a[i].r) { a[i].n=m; a[i].sum=m; } if(a[i].l == a[i].r) return ; int mid = (a[i].l+a[i].r)/2; if(x>mid) insert(i<<1|1,x,m); else insert(i<<1,x,m); a[i].sum = a[i<<1].sum+a[i<<1|1].sum; a[i].n = max(a[i<<1].n,a[i<<1|1].n);}int make_max(int l,int r,int i){ if(a[i].l==l&&a[i].r==r) return a[i].n; int mid=(a[i].l+a[i].r)/2; if(l>mid) return make_max(l,r,i<<1|1); else if(r<=mid) return make_max(l,r,i<<1); else return max(make_max(l,mid,i<<1),make_max(mid+1,r,i<<1|1));}int make_sum(int l,int r,int i){ if(a[i].l==l&&a[i].r==r) return a[i].sum; int mid=(a[i].l+a[i].r)/2; if(l>mid) return make_sum(l,r,i<<1|1); else if(r<=mid) return make_sum(l,r,i<<1); else return make_sum(l,mid,i<<1)+make_sum(mid+1,r,i<<1|1);}int main(){ int n,m,num; int l,r,c; scanf("%d%d",&n,&m); init(1,n,1); for(int i=1; i<=n; i++) { scanf("%d",&num); insert(1,i,num); } while(m--) { scanf("%d%d%d",&c,&l,&r); if(c==1) insert(1,l,r); else if(c==2) cout<<make_sum(l,r,1)<<endl; else if(c==3) cout<<make_max(l,r,1)<<endl; } return 0;}

上一篇：pycharm 教程（一）安装和首次使用

下一篇：C#窗体实现IPconfig/All功能