anideahe @ 2020-08-11 17:09:57
#include<bits/stdc++.h>
using namespace std;
int n,M;
int t[5000001];
int a[5000001];
int s[5000001],lm[5000001],rm[5000001],m[5000001];
void push(int x){
s[x]=s[x<<1]+s[x<<1|1];
lm[x]=max(s[x<<1]+lm[x<<1|1],lm[x<<1]);
rm[x]=max(rm[x<<1|1],rm[x<<1]+s[x<<1|1]);
m[x]=max(max(m[x<<1],m[x<<1|1]),lm[x<<1|1]+rm[x<<1]);
return ;
}
void build(int x,int l,int r){
if(l==r) {
s[x]=lm[x]=rm[x]=m[x]=a[x];
return ;
}
int mid=(r+l)>>1;
build(x<<1,l,mid);
build(x<<1|1,mid+1,r);
push(x);
}
void modify(int x,int l,int r,int ql,int qr,int w){
if(l>=ql&&r<=qr) {
s[x]=lm[x]=rm[x]=m[x]=w;
return ;
}
int mid=(l+r)>>1;
if(ql<=mid) modify(x<<1,l,mid,ql,qr,w);
if(qr>mid) modify(x<<1|1,mid+1,r,ql,qr,w);
push(x);
}
void search(int x,int l,int r,int ql,int qr){
if(l>=ql&&r<=qr) return ;
int mid=(l+r)>>1;
if(qr<=mid) search(x<<1,l,mid,ql,qr);
else if(ql>mid) search(x<<1|1,mid+1,r,ql,qr);
else {
search(x<<1,l,mid,ql,qr);
search(x<<1|1,mid+1,r,ql,qr);
push(x);
}
}
int main(){
cin>>n>>M;
for(int i=1;i<=n;i++)
cin>>a[i];
build(1,1,n);
for(int i=1;i<=M;i++){
int k,c,b;
cin>>k>>c>>b;
if(k==1){
if(c>b) swap(c,b);
search(1,1,n,c,b);
cout<<m[1]<<endl;
}
else modify(1,1,n,c,c,b);
}
return 0;
}
by ctj12461 @ 2020-08-11 17:34:58
@嘻梦th 你这样肯定不行啊,因为search()
中一直都是在push
线段树上的结点,自然无法查询,m[1]
也一直是整个区间的最大值。
by ctj12461 @ 2020-08-11 17:37:21
@嘻梦th 使用结构体是比较方便,你用几个pair
套娃或者tuple
都是可以的,唯独void
不行。