3981 动态最大子段和
时间限制: 1 s
空间限制: 128000 KB
题目等级 : 钻石 Diamond
题目描述 Description
题目还是简单一点好...
有n个数，a[1]到a[n]。
接下来q次查询，每次动态指定两个数l,r，求a[l]到a[r]的最大子段和。
子段的意思是连续非空区间。
输入描述 Input Description
第一行一个数n。
第二行n个数a[1]~a[n]。
第三行一个数q。
以下q行每行两个数l和r。
输出描述 Output Description
q行，每行一个数，表示a[l]到a[r]的最大子段和。
样例输入 Sample Input
7
2 3 -233 233 -23 -2 233
4
1 7
5 6
2 5
2 3
样例输出 Sample Output
441
-2
233
3
数据范围及提示 Data Size & Hint
对于50%的数据，q*n<=10000000。
对于100%的数据，1<=n<=200000，1<=q<=200000。
a[1]~a[n]在int范围内，但是答案可能超出int范围。
数据保证1<=l<=r<=n。
空间128M，时间1s。
我不会告诉你数据里有样例
/* 线段树区间操作GSS 一段长的区间的 GSS 有三种情况： 1 完全在左子区间 2 完全在右子区间 3 横跨左右区间 前两种情况可使用子区间的 GSS，但如何处理第三种情况？ 注意到我们可以把区间拆成两部分，这两部分是不相关的。 所以我们需要维护一个区间的“最大左子段和”和“最大右子段和”。 gss = MAX{l.gss,r.gss,l.rgss + r.lgss} 由 GSS 一直推下来,对于每个节点,我们一共需要设计4个状态。 1 GSS：最大子段和 2 LGSS：最大左子段和 3 RGSS：最大右子段和 4 SUM：整段和 这里我用了结构体存储（元元真厉害啊！） */ #include<iostream> #include<cstdio> #include<cstring> #define ll long long #define maxn 2000010 using namespace std; ll n,a[maxn],q,x,y,ans; struct node{ ll l,r,dis,mx,lmx,rmx; }tre[maxn>>2]; ll init() { ll x=0,f=1;char c=getchar(); while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} return x*f; } void build(int now,ll l,ll r) { tre[now].l=l;tre[now].r=r; if(l==r) { tre[now].dis=init(); tre[now].lmx=tre[now].rmx=tre[now].mx=tre[now].dis; return ; } ll mid=(l+r)>>1; build(now<<1,l,mid); build(now<<1|1,mid+1,r); //下面是重点之一，要注意。 tre[now].lmx=max(tre[now<<1].lmx,tre[now<<1].dis+tre[now<<1|1].lmx); tre[now].rmx=max(tre[now<<1|1].rmx,tre[now<<1|1].dis+tre[now<<1].rmx); tre[now].mx=max(tre[now<<1].rmx+tre[now<<1|1].lmx,max(tre[now<<1].mx,tre[now<<1|1].mx)); tre[now].dis=tre[now<<1].dis+tre[now<<1|1].dis; } node query(int now,ll l,ll r) { node ans; if(l==tre[now].l&&r==tre[now].r) return tre[now]; ll mid=(tre[now].l+tre[now].r)>>1; if(l>mid) return query(now<<1|1,l,r); else if(r<=mid) return query(now<<1,l,r); else//就是这里咋也不会写，递归找边界思路不清晰 { node lch=query(now<<1,l,mid); node rch=query(now<<1|1,mid+1,r); ans.lmx=max(lch.lmx,lch.dis+rch.lmx); ans.rmx=max(rch.rmx,rch.dis+lch.rmx); ans.mx=max(max(lch.mx,rch.mx),lch.rmx+rch.lmx); } return ans; } int main() { n=init(); build(1,1,n); q=init(); for(int i=1;i<=q;i++) { x=init();y=init(); printf("%lld ",query(1,x,y).mx); } return 0; }