试题 ASGO-7 算法训练操作格子

本文主要是介绍试题 ASGO-7 算法训练操作格子，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接试题 ASGO-7 算法训练操作格子
线段树详解看这里——> 线段树详解

题目描述

资源限制
时间限制：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。

解题思路

主要是记录线段树的板子，在代码里给注释。

程序代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define ls rt<<1
#define rs rt<<1|1
#define ll long long
#define mid ((tree[rt].l+tree[rt].r)>>1)
//上面这几个define应该是叫做宏定义，方便后面写的代码简洁一点
using namespace std;
struct arr {int l,r,tag1,maxx;ll sum,tag;
}tree[410005];
//线段树大概要开比原数组大四倍的空间
int n,m,a[100005];//读入优化
inline ll read() {int x=0,w=1;char ch=0;while(ch!='0'&&(ch<'0'||ch>'9')) ch=getchar();if(ch=='-') w=-1,ch=getchar();while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch-48),ch=getchar();return x*w;
}//上传最大值和区间总和
inline void pushup(int rt) {//把子树的总和更新到父节点tree[rt].sum=(tree[ls].sum+tree[rs].sum);//父节点的最大值来自于左右子树的最大值中最大的那个tree[rt].maxx=max(tree[rs].maxx,tree[ls].maxx);
}//下传lazy tag，在这道题不用，就不用管
inline void pushdown(int rt) {if(tree[rt].tag) {tree[ls].tag=tree[rt].tag;tree[rt].tag=tree[rt].tag;tree[ls].sum=((tree[ls].r-tree[ls].l+1)*tree[ls].tag);tree[rs].sum=((tree[rs].r-tree[rs].l+1)*tree[rs].tag);tree[rt].maxx=(tree[rt].tag,tree[rt].maxx);tree[rs].maxx=(tree[rs].tag,tree[rs].maxx);tree[ls].maxx=(tree[ls].maxx,tree[ls].tag);tree[rt].tag=0;}
} //建立一棵二叉树
void build(int l,int r,int rt) {tree[rt].l=l;tree[rt].r=r;//记录当前这个节点的左端点和右端点的标号if(l==r) {tree[rt].sum=a[l];tree[rt].maxx=a[l];return ;}//如果左右端点相等，说明到叶子节点了，这个时候就把叶子节点给赋值int midd=(l+r)>>1;build(l,midd,ls);build(midd+1,r,rs);//往左递归，往右递归。ls的序号是根节点的两倍，rs的序号是根节点的两倍加一pushup(rt);//上传一下最大值和最小值
}
void updata(int l,int r,int c,int rt) {if(l==tree[rt].l&&tree[rt].r==r) {tree[rt].sum=(tree[rt].r-tree[rt].l+1)*c;tree[rt].tag=c;tree[rt].maxx=c;return ;}/*上面操作是更新区间的和，还有就是区间的最大值。因为本道题更新的是一个点，可以看做区间长度为一必将递归到最底层所以maxx直接改为c。*///pushdown(rt);if(r<=mid) updata(l,r,c,ls);else if(l>mid) updata(l,r,c,rs);else {updata(l,mid,c,ls);updata(mid+1,r,c,rs);}/*如果当前更新区间的右端点比当前rt节点存储的中间点还要小，说明要更新的节点在左子树反之在右子树还有一种情况，是当前更新的区间在左子树和右子树中都有，那就左右子树都递归*/pushup(rt);//上传最大值和总和
}
ll query1(int l,int r,int rt) {if(l==tree[rt].l&&tree[rt].r==r) return tree[rt].sum;//如果查询的l和r刚好符合rt覆盖的区间，直接返回总和//pushdown(rt);ll ans=0;//记录下面递归时返回的区间总和，累加if(r<=mid) ans+=query1(l,r,ls);else if(l>mid) ans+=query1(l,r,rs);else{ans+=query1(l,mid,ls);ans+=query1(mid+1,r,rs);}pushup(rt);return ans;//把返回的总和传上去
}
ll query2(int l,int r,int rt) {if(l==tree[rt].l&&tree[rt].r==r) return tree[rt].maxx;//同上面的查询一样，这里返回最大值//pushdown(rt);if(r<=mid) return query2(l,r,ls);else if(l>mid) return query2(l,r,rs);else{return max(query2(l,mid,ls),query2(mid+1,r,rs));}//与更新操作的那一样，只不过这里要比较左右子树中哪个返回的值更大pushup(rt);
}
int main() {freopen("ALGO-7.in","r",stdin);freopen("ALGO-7.out","w",stdout);int p,x,y;//cin>>n>>m;n=read();m=read();for(int i=1;i<=n;++i) a[i]=read();build(1,n,1);//建立子树for(int i=1;i<=m;++i) {//cin>>p>>x>>y;p=read();x=read();y=read();if(p==1) updata(x,x,y,1);//更新x到x这个点的值改为y值if(p==2) { ll xx=query1(x,y,1);printf("%d\n",xx);//查询x到y的总和}if(p==3) {	ll xx=query2(x,y,1);printf("%d\n",xx);//查询x到y的最大值}}return 0;
}

读入优化

inline ll read() {int x=0,w=1;char ch=0;while(ch!='0'&&(ch<'0'||ch>'9')) ch=getchar();if(ch=='-') w=-1,ch=getchar();while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch-48),ch=getchar();return x*w;
}