线段树
询问给定区间最大连续序列和，相等的值不能重复计算，可以为空序列。
这题需要离线，将区间的右端点按照从小到大排序，将原序列依次加入线段树中。
假设线段树中已加入 a[1] ... a[i]，在线段树中，叶子结点我们维护 a[j] ... a[i] 序列的和 Sum
如：
1. a[1] + a[2] + ... + a[i]
2. a[2] + a[2] + ... + a[i]
...
i. a[i]
同时还需要维护出现过的和的最大值 Max
在非叶子结点，Sum 便等于左右儿子 Sum 的最大值，Max 也等于左右儿子 Max 的最大值。
在更新 i+1 时，由于相同值不能重复计算，所以 a[i+1] 只能更新值 a[i+1] 最近一次出现的位置 j + 1 到 i 这段区间。
即最大的 j < i+1 ， a[j] == a[i+1]， 则 pre[i+1] = j，更新后：
1. a[1] + a[2] + ... + a[i]
2. a[2] + a[2] + ... + a[i]
...
j. a[j] + a[j+1] + ... + a[i]
j+1. a[j+1] + a[j+2] + ... + a[i] + a[i+1]
...
i. a[i] + a[i+1]
i+1. a[i+1]
于是，为了维护 Sum 和 Max，需要引入两个懒标记 LazySum 和 LazyMax，分别表示更新这段区间的值的和，以及这个和出现过的最大值。
当我们用 a[i+1] 更新当前整个区间时：
Sum += a[i+1]
Max = max{Sum, Max}
LazySum += a[i+1]
LazyMax = max{LazySum, LazyMax}
当我们下放懒标记时：
son.Max = max{son.Max, son.Sum + fat.LazyMax}
son.Sum += fat.LazySum
son.LazyMax = max{son.LazyMax, son.LazySum + fat.LazyMax}
son.LazySum += fat.LazySum
那么对于区间[l, r]，当我们更新到 r 以后，查询线段树[l, r]这段区间的 Max 即可。
1 #include <cstdio> 2 #include <cstring> 3 #include <cmath> 4 #include <queue> 5 #include <algorithm> 6 7 using namespace std; 8 9 #define MAXN 100010 10 #define INF 0x3f3f3f3f 11 #define MAX(a,b) (a>b?a:b) 12 #define MIN(a,b) (a<b?a:b) 13 #define ABS(m) (m<0?-m:m) 14 #define mo 1000000007 15 typedef long long LL; 16 17 int n,q,a[MAXN]; 18 int Index[MAXN*2],pre[MAXN]; 19 LL ans[MAXN]; 20 21 struct QUERY 22 { 23 int l,r,i; 24 bool operator<(const QUERY &z) const{ 25 return r<z.r; 26 } 27 }qy[MAXN]; 28 29 struct SegmentTree 30 { 31 LL Max,Sum,LazyMax,LazySum; 32 SegmentTree(int val=0):Max(val),Sum(val){ LazyMax=LazySum=0; } 33 34 SegmentTree operator+(const SegmentTree &z) const{ 35 SegmentTree res; 36 res.Max=MAX(Max,z.Max); 37 res.Sum=MAX(Sum,z.Sum); 38 return res; 39 } 40 }tree[MAXN*4]; 41 42 void Update(int i) 43 { 44 tree[i*2].Max=MAX(tree[i*2].Max,(tree[i*2].Sum+tree[i].LazyMax)); 45 tree[i*2].Sum+=tree[i].LazySum; 46 tree[i*2].LazyMax=MAX(tree[i*2].LazyMax,(tree[i*2].LazySum+tree[i].LazyMax)); 47 tree[i*2].LazySum+=tree[i].LazySum; 48 tree[i*2+1].Max=MAX(tree[i*2+1].Max,(tree[i*2+1].Sum+tree[i].LazyMax)); 49 tree[i*2+1].Sum+=tree[i].LazySum; 50 tree[i*2+1].LazyMax=MAX(tree[i*2+1].LazyMax,(tree[i*2+1].LazySum+tree[i].LazyMax)); 51 tree[i*2+1].LazySum+=tree[i].LazySum; 52 tree[i].LazyMax=tree[i].LazySum=0; 53 } 54 55 void Modify(int i,int l,int r,int s,int t,LL val) 56 { 57 if(s<=l && r<=t){ 58 tree[i].LazySum+=val; 59 tree[i].LazyMax=MAX(tree[i].LazyMax,tree[i].LazySum); 60 tree[i].Sum+=val; 61 tree[i].Max=MAX(tree[i].Max,tree[i].Sum); 62 return; 63 } 64 Update(i); 65 int mid=(l+r)>>1; 66 if(l<=t&&mid>=s) Modify(i*2,l,mid,s,t,val); 67 if(mid<t&&r>=s) Modify(i*2+1,mid+1,r,s,t,val); 68 tree[i]=tree[i*2]+tree[i*2+1]; 69 } 70 71 SegmentTree Getans(int i,int l,int r,int s,int t) 72 { 73 if(s<=l && r<=t) return tree[i]; 74 Update(i); 75 int mid=(l+r)>>1; SegmentTree res1,res2; 76 if(l<=t&&mid>=s) res1=Getans(i*2,l,mid,s,t); 77 if(mid<t&&r>=s) res2=Getans(i*2+1,mid+1,r,s,t); 78 return res1+res2; 79 } 80 81 void Init() 82 { 83 scanf("%d",&n); 84 for(int i=1;i<=n;++i) scanf("%d",a+i); 85 for(int i=1;i<=n;++i){ 86 pre[i]=Index[a[i]+100000]; 87 Index[a[i]+100000]=i; 88 } 89 } 90 91 void Query() 92 { 93 int i,j; 94 SegmentTree res; 95 scanf("%d",&q); 96 for(i=1;i<=q;++i){ 97 scanf("%d%d",&qy[i].l,&qy[i].r); 98 qy[i].i=i; 99 } 100 sort(qy+1,qy+1+q); 101 for(i=j=1;i<=n;++i){ 102 Modify(1,1,n,pre[i]+1,i,a[i]); 103 for(;j<=q&&qy[j].r<=i;++j){ 104 res=Getans(1,1,n,qy[j].l,i); 105 ans[qy[j].i]=MAX(ans[qy[j].i],res.Max); 106 } 107 } 108 for(i=1;i<=q;++i) printf("%lld\n",ans[i]); 109 } 110 111 int main() 112 { 113 Init(); 114 Query(); 115 return 0; 116 }
SPOJ - GSS2 - Can you answer these queries II
SPOJ - GSS2 - Can you answer these queries II
原文：http://www.cnblogs.com/orenjisora/p/5002528.html
