算法训练 操作格子

算法训练 操作格子 时间限制：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; }