Link

GSS1 - Can you answer these queries I

Solve

GSS1 - Can you answer these queries III的降级版，不带修改的，直接用线段树即可。

Code

直接改了下3的代码我懒

#include<bits/stdc++.h>
using namespace std;
const int maxn=50005;
int N,Q,a[maxn];
struct node{
	int l,r,sum,lmax,rmax,max;
}c[maxn<<2];

inline int read(){
	int ret=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
	while(ch<='9'&&ch>='0')ret=ret*10+ch-'0',ch=getchar();
	return ret*f;
}
void pushup(int x){
	c[x].sum=c[x<<1].sum+c[x<<1|1].sum;
	c[x].lmax=max(c[x<<1].lmax,c[x<<1].sum+c[x<<1|1].lmax);
	c[x].rmax=max(c[x<<1|1].rmax,c[x<<1|1].sum+c[x<<1].rmax);
	c[x].max=max(c[x<<1].max,max(c[x<<1|1].max,c[x<<1].rmax+c[x<<1|1].lmax)); 
}
void build(int x,int l,int r){
	c[x].l=l,c[x].r=r;
	if(l==r){
		c[x].sum=c[x].lmax=c[x].rmax=c[x].max=a[l];
		return ;
	}
	int mid=(r-l>>1)+l;
	build(x<<1,l,mid);
	build(x<<1|1,mid+1,r);
	pushup(x);
}
void change(int x,int u,int v){
	if(c[x].l==c[x].r){
		c[x].lmax=c[x].rmax=c[x].max=c[x].sum=v;
		return ;
	}
	int mid=(c[x].r-c[x].l>>1)+c[x].l;
	if(u<=mid)change(x<<1,u,v);
	else change(x<<1|1,u,v);
	pushup(x);
}
node query(int x,int L,int R){
	if(L<=c[x].l&&c[x].r<=R)return c[x];
	int mid=(c[x].r-c[x].l>>1)+c[x].l;
	if(R<=mid)return query(x<<1,L,R);
	if(mid<L)return query(x<<1|1,L,R);
	node L_tree=query(x<<1,L,mid),R_tree=query(x<<1|1,mid+1,R),res;
	res.sum=L_tree.sum+R_tree.sum;
	res.lmax=max(L_tree.lmax,L_tree.sum+R_tree.lmax);
	res.rmax=max(R_tree.rmax,R_tree.sum+L_tree.rmax);
	res.max=max(L_tree.rmax+R_tree.lmax,max(L_tree.max,R_tree.max));
	return res;
}
int main(){
	freopen("SP1716.in","r",stdin);
	freopen("SP1716.out","w",stdout);
	N=read();
	for(int i=1;i<=N;i++)a[i]=read();
	Q=read();
	build(1,1,N);
	while(Q--){
		 int /*op=read(),*/x=read(),y=read();
//		 if(op==0)change(1,x,y);
//		 else 
		 printf("%d\n",query(1,x,y).max);
	}
	return 0;
}