蓝桥杯操作格子（单点更新）

60 阅读 0 评论 40 点赞

我是靠谱客的博主饱满钥匙，最近开发中收集的这篇文章主要介绍蓝桥杯操作格子（单点更新），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

算法训练操作格子

时间限制：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操作的结果。

样例输入

样例输出

6

 3

数据规模与约定

对于20%的数据n <= 100，m <= 200。

对于50%的数据n <= 5000，m <= 5000。

对于100%的数据1 <= n <= 100000，m <= 100000，0 <= 格子权值 <= 10000。

线段树的单点更新，每次更新的时候既要更新和，又要更新最大值，在遇到查询问题的时候要考虑树状数组和线段树操作。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <set>
#include <cmath>
#include <queue>
#include <map>
#define MAXN 100010
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
using namespace std;
int t[MAXN<<2],s[MAXN<<2];
int a[MAXN+10];
int n,m;
void pushup(int rt){
t[rt] = t[rt<<1]+t[rt<<1|1];
s[rt] = max(s[rt<<1],s[rt<<1|1]);
}
void b(int l,int r,int rt){
if(l==r){
t[rt] = a[l];
s[rt] = a[l];
return;
}
int mid = (l+r)>>1;
b(lson);
b(rson);
pushup(rt);
}
void update(int l,int r,int rt,int k,int x){
if(l==r&&l==k){
s[rt] = x;
t[rt] = x;
return;
}
int mid=(l+r)>>1;
if(k<=mid)
update(lson,k,x);
if(k>mid)
update(rson,k,x);
pushup(rt);
}
int queryt(int l,int r,int rt,int ll,int rr){
if(ll==l&&r==rr)
return t[rt];
int mid = (l+r)>>1;
if(rr<=mid)
return queryt(lson,ll,rr);
else if(ll>mid)
return queryt(rson,ll,rr);
else {
return queryt(lson,ll,mid)+queryt(rson,mid+1,rr);
}
}
int querys(int l,int r,int rt,int ll,int rr){
if(ll==l&&r==rr)
return s[rt];
int mid = (l+r)>>1;
if(rr<=mid)
return querys(lson,ll,rr);
else if(ll>mid)
return querys(rson,ll,rr);
else {
return max(querys(lson,ll,mid),querys(rson,mid+1,rr));
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i = 1;i <= n;i++){
scanf("%d",&a[i]);
}
b(1,n,1);
while(m--){
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
if(u==1){
update(1,n,1,v,w);
}
if(u==2){
printf("%dn",queryt(1,n,1,v,w));
}
if(u==3){
printf("%dn",querys(1,n,1,v,w));
}
}
return 0;
}