有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 31 2 3 42 1 31 4 33 1 4 样例输出63 数据规模与约定对于20%的数据n <= 100,m <= 200。
对于50%的数据n <= 5000,m <= 5000。
对于100%的数据1 <= n <= 100000,m <= 100000,0 <= 格子权值 <= 10000。
直接贴上代码:
#include<iostream>#define MAX 100000using namespace std;struct seg_TreeNode{ int low, high;//区间左右端点 int value, max;//value在叶子节点表示权值,非叶子节点表示区间权值和,max表示区间内最大值}tree[4*MAX];void initTree(int num,int low, int high){ if(low==high) { tree[num].low = tree[num].high = low; cin >> tree[num].value; tree[num].max =tree[num].value; return; } tree[num].low = low; tree[num].high = high; int mid = (low + high) >> 1; initTree(2 * num, low, mid); initTree(2 * num+1, mid+1,high); tree[num].max = tree[num * 2].max > tree[num * 2 + 1].max ? tree[num * 2].max : tree[num * 2 + 1].max; tree[num].value = tree[num * 2].value + tree[num * 2 + 1].value;//此处线段树建立采用后续遍历,因为区间的权值和需要知道左区间和右区间的权值和。}void update(int num, int x, int y){ if (tree[num].low == tree[num].high) { tree[num].value = y; tree[num].max = y; return; } int mid = tree[num * 2].high; if (mid >= x) update(num * 2, x, y); if (mid < x) update(num * 2 + 1, x, y); tree[num].value = tree[num * 2].value + tree[num * 2 + 1].value; tree[num].max = tree[num*2].max < tree[num*2+1].max ? tree[num*2+1].max: tree[num*2].max; return;}int query1(int num, int low, int high)//最大值{ if (tree[num].low == low&&tree[num].high == high) return tree[num].max; int mid = tree[num * 2].high; if (mid >= high) return query1(num * 2, low, high); if (mid < low) return query1(num * 2 + 1, low, high); int le=query1(num * 2, low, mid); int ri=query1(num * 2 + 1, mid + 1, high); return le > ri?le:ri;}int query2(int num, int low, int high)//区间和{ if (tree[num].low == low&&tree[num].high == high) return tree[num].value; int mid = tree[num * 2].high; if (mid >= high) return query2(num * 2, low, high); if (mid < low) return query2(num * 2 + 1, low, high); int le = query2(num * 2, low, mid); int ri = query2(num * 2 + 1, mid + 1, high); return le+ri;}int main(){ int a, b, c; int m, n; cin >> m >> n; initTree(1, 1, m); for (int i = 0;i < n;i++) { cin >> a >> b >> c; switch (a) { case 1:update(1, b, c);break; case 2:cout<<query2(1, b, c)<<endl;break; case 3:cout<<query1(1, b, c)<<endl;break; } } return 0;}
新闻热点
疑难解答