文件详细信息

下载本文件

本文件的大小为 1668 字节。

#include<cstdio>
void read(int&num){
	bool flag=true;
	int ch=getchar();
	num=0;
	while(ch<48||ch>57){
		if(ch=='-')flag=false;
		ch=getchar();
	}
	while(ch>=48&&ch<=57)num=(num<<3)+(num<<1)+(ch^48),ch=getchar();
	flag||(num=-num);
}
void write(int a){
	static int ch[25],cnt;
	if(a<0)putchar('-'),a=-a;
	if(a==0)putchar('0');
	cnt=0;
	while(a)ch[++cnt]=a%10|48,a/=10;
	while(cnt)putchar(ch[cnt--]);
}
int max(const int a,const int b){
	return a>b?a:b;
}
void swap(int&a,int&b){
	int temp=a;
	a=b;
	b=temp;
}
const int maxn=500005;
int n,m,k,a,b,s,p;
struct Seg{
	int sum,l,r,m;
}t[maxn<<2];
Seg pushup(Seg l,Seg r){
	Seg u;
	u.sum=l.sum+r.sum;
	u.l=max(l.l,l.sum+r.l);
	u.r=max(r.r,r.sum+l.r);
	u.m=max(max(l.m,r.m),l.r+r.l);
	return u;
}
void build(int u,int l,int r){
	if(l==r){
		read(t[u].sum);
		t[u].l=t[u].r=t[u].m=t[u].sum;
		return;
	}
	int m=(l+r)>>1;
	build(u<<1,l,m);
	build(u<<1|1,m+1,r);
	t[u]=pushup(t[u<<1],t[u<<1|1]);
}
Seg query(int u,int l,int r,int ql,int qr){
	if(ql<=l&&r<=qr)return t[u];
	int m=(l+r)>>1;
	if(m>=qr)return query(u<<1,l,m,ql,qr);
	if(m<ql)return query(u<<1|1,m+1,r,ql,qr);
	return pushup(query(u<<1,l,m,ql,qr),query(u<<1|1,m+1,r,ql,qr));
}
void modify(int u,int l,int r,int x,int val){
	if(l==r){
		t[u]={val,val,val,val};
		return;
	}
	int m=(l+r)>>1;
	if(x<=m)modify(u<<1,l,m,x,val);
	else modify(u<<1|1,m+1,r,x,val);
	t[u]=pushup(t[u<<1],t[u<<1|1]);
}
int main(){
	read(n),read(m);
	build(1,1,n);
	while(m--){
		read(k);
		if(k==1){
			read(a),read(b);
			if(a>b)swap(a,b);
			Seg ans=query(1,1,n,a,b);
			write(max(max(ans.l,ans.r),ans.m)),putchar('\n');
		}else{
			read(p),read(s);
			modify(1,1,n,p,s);
		}
	}
	return 0;
}