SPOJ GSS3 Can you answer these queries III ——线段树

时间:2022-06-30 12:42:18

【题目分析】

GSS1的基础上增加修改操作。

同理线段树即可,多写一个函数就好了。

【代码】

#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib> #include <map>
#include <set>
#include <queue>
#include <string>
#include <iostream>
#include <algorithm> using namespace std; #define maxn 2000005
#define eps 1e-8
#define db double
#define ll long long
#define inf 0x3f3f3f3f
#define F(i,j,k) for (ll i=j;i<=k;++i)
#define D(i,j,k) for (ll i=j;i>=k;--i) void Finout()
{
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
// freopen("wa.txt","w",stdout);
#endif
} ll Getll()
{
ll x=0,f=1; char ch=getchar();
while (ch<'0'||ch>'9') {if (ch=='-') f=-1; ch=getchar();}
while (ch>='0'&&ch<='9') {x=x*10+ch-'0'; ch=getchar();}
return x*f;
} ll buf=100005,next[maxn],pos[maxn]; struct Node{
ll lx,rx,mx,sum;
Node operator + (Node x)
{
Node ret;
ret.lx=max(lx,sum+x.lx);
ret.rx=max(x.sum+rx,x.rx);
ret.sum=sum+x.sum;
ret.mx=max(max(mx,x.mx),max(rx+x.lx,max(ret.lx,ret.rx)));
return ret;
}
}t[maxn]; ll n,a[maxn],q,L,R,x,c; struct Problem{ll l,r,id,ans;}p[maxn]; bool cmp1(Problem x,Problem y)
{return x.l==y.l?x.r<y.r:x.l<y.l;}
bool cmp2(Problem x,Problem y)
{return x.id<y.id;} void Build(ll o,ll l,ll r)
{
if (l==r)
{
t[o].lx=t[o].rx=t[o].mx=t[o].sum=a[l];
return ;
}
ll mid=l+r>>1;
Build(o<<1,l,mid);
Build(o<<1|1,mid+1,r);
t[o]=t[o<<1]+t[o<<1|1];
} Node Query(ll o,ll l,ll r)
{
if (L<=l&&r<=R) return t[o];
ll mid=l+r>>1;
if (L>mid) return Query(o<<1|1,mid+1,r);
else if (R<=mid) return Query(o<<1,l,mid);
else return Query(o<<1,l,mid)+Query(o<<1|1,mid+1,r);
} void Modify(ll o,ll l,ll r)
{
if (l==r)
{
t[o].lx=t[o].rx=t[o].mx=t[o].sum=c;
return ;
}
ll mid=l+r>>1;
if (x<=mid) Modify(o<<1,l,mid);
else Modify(o<<1|1,mid+1,r);
t[o]=t[o<<1]+t[o<<1|1]; } int main()
{
Finout(); n=Getll();
// printf("%lld\n",n);
F(i,1,n) a[i]=Getll();
// F(i,1,n) printf("%lld ",a[i]);
// printf("\n");
Build(1,1,n); q=Getll();
F(i,1,q)
{
ll opt=Getll();
switch (opt)
{
case 1:
L=Getll();
R=Getll();
printf("%lld\n",Query(1,1,n).mx);
break;
case 0:
x=Getll();
c=Getll();
Modify(1,1,n);
break;
}
}
}