不知道第几次回顾了，每次回顾感觉都有新的收获
这题YYZ认为非常的简单，我们一起去%%%她吧（洛谷$id: 54050$）
题面
给出$n$个数，有$q$个询问，求最大子段和，注意相同的数只算一次
做法
考虑神奇的转化
定义区间$[l,r]$的最大子段和为$A(l, r)$
定义左端点在$l$，右端点在$[l,r]$之间的区间和（重复元素记一次）的最大值为$P(l, r)$
定义左端点在$l$，右端点为$r$的区间和（重复元素记一次）为$S(l,r)$
那么，我们有转化$A(l, r) = max(P(l, r), P(l + 1, r), ..., P(r, r))$
这是显然成立的，相当于根据子段和的左端点进行分类后求最大值
一个疯狂的想法
我们枚靠$r$
每次$r$往右扩展时，
如果我们能动态地维护$P(l,r)...P(r,r)$
那么，对于每个$r$而言，
只要我们能用一种能快速求出$max(P(l,r), P(l +1, r),...,P(r,r))$的数据结构
我们就能回答询问右端点是$r$的所有询问
理下思路：
1.给所有查询按右端点排序
2.枚举右端点
3.在枚举的途中动态地维护$P(l,r)...P(r,r)$
（$P(l,r)...P(r,r)$对应区间$[l,r]$）
4.用线段树快速回答右端点是$r$的询问
由定义：$P(l,r) = max(S(l,l), S(l,l+1),S(l,l+2),.....,S(l,r))$
考虑当$r$从$i-1$移动到$i$时，有$P(l,i) = max(P(l, i - 1), S(l, i))$（由定义）
我们从这个式子考虑维护
记$val[i]$表示$i$位置的元素值
记$pre[i]$表示满足$val[i] = val[j]$和$j < i$的最大的$j$
对于$[1, pre[i]]$的$j$而言，由于重复元素不计数，有$S(j,i) = S(j, i - 1)$
即$P(j, i) = P(j, i - 1)$，因此，线段树维护时跳过这一段即可保证不重
对于$[pre[j] + 1, i]$的$j$而言，有$S(j, i) = S(j, i - 1) + val[j]$
我们只要维护$S(j, i)$和$P(j, i)$就可以了
但是，由于是区间修改，因此我们要考虑合理地设计标记来维护
（假设$r$枚举到$i$）
不妨设$tag[j]$为为了维护$S(j, i)$而生的懒惰标记
设$lazy[j]$为为了维护$P(j, i)$而生的懒惰标记
注意之间的相对顺序即可，具体看代码注释
#include <cstdio>
#include <iostream>
#include <algorithm>
#define rem template <typename re>
#define ls (p << 1)
#define rs (p << 1 | 1)
#define ll long long
#define sid 800005
using namespace std; char RR[];
extern inline char gc() {
static char *S = RR + , *T = RR + ;
if(S == T) S = RR, fread(RR, , , stdin);
return *S ++;
}
inline int read() {
int p = , w = ; char c = gc();
while(c > '' || c < '') { if(c == '-') w = -; c = gc(); }
while(c >= '' && c <= '') { p = p * + c - ''; c = gc(); }
return p * w;
} int n, m, ret;
int val[sid], pre[sid];
ll ans[sid]; struct Seg {
ll P, S, tag, lazy;
//t[p].P -> max(P(l,i)...P(r,i))
//t[p].S -> max(S(l,i)...S(r,i))
//t[p].tag -> 给[l, r]的S未加的值
//t[p].lazy -> 所有tag中最大的那个值
} tr[sid]; struct Question {
int l, r, id;
friend bool operator < (Question a, Question b) {
return a.r < b.r;
}
} q[sid]; void Pushdown(int p) {
if(!tr[p].tag && !tr[p].lazy) return;
tr[ls].P = max(tr[ls].P, tr[ls].S + tr[p].lazy);
//取S最大值和lazy最大值相加绝对是最大值
tr[ls].lazy = max(tr[ls].lazy, tr[ls].tag + tr[p].lazy);
//更新lazy
tr[ls].S += tr[p].tag; tr[ls].tag += tr[p].tag;
//依照定义
tr[rs].P = max(tr[rs].P, tr[rs].S + tr[p].lazy);
tr[rs].lazy = max(tr[rs].lazy, tr[rs].tag + tr[p].lazy);
tr[rs].S += tr[p].tag; tr[rs].tag += tr[p].tag;
tr[p].tag = ; tr[p].lazy = ;
} void Update(int p) {
tr[p].S = max(tr[ls].S, tr[rs].S);
tr[p].P = max(tr[ls].P, tr[rs].P);
} void Modify(int p, int l, int r, int ml, int mr, int mc) {
if(ml <= l && mr >= r) {
tr[p].tag += mc; tr[p].S += mc;
//对[l,r]中所有数+mc，则t[p].S += mc
//自然t[p].tag += mc
tr[p].lazy = max(tr[p].lazy, tr[p].tag);
//定义
tr[p].P = max(tr[p].S, tr[p].P);
//定义
return;
}
Pushdown(p);
int mid = (l + r) >> ;
if(ml <= mid) Modify(p << , l, mid, ml, mr, mc);
if(mr > mid) Modify(p << | , mid + , r, ml, mr, mc);
Update(p);
} ll Query(int p, int l, int r, int ml, int mr) {
if(ml <= l && mr >= r) return tr[p].P;
Pushdown(p); ll ans = -;
int mid = (l + r) >> ;
if(ml <= mid) ans = Query(p << , l, mid, ml, mr);
if(mr > mid) ans = max(ans, Query(p << | , mid + , r, ml, mr));
return ans;
} int main() {
n = read();
for(int i = ; i <= n; i ++) val[i] = read();
m = read();
for(int i = ; i <= m; i ++)
q[i].l = read(), q[i].r = read(), q[i].id = i;
sort(q + , q + m + ); int tail = ;
for(int i = ; i <= n; i ++) {
if(tail > m) break;
int nv = val[i] + ; //注意负数
Modify(, , n, pre[nv] + , i, val[i]);
pre[nv] = i;
while(q[tail].r == i) ans[q[tail].id] = Query(, , n, q[tail].l, i), tail ++;
}
for(int i = ; i <= m; i ++) printf("%lld\n", ans[i]);
return ;
}