一个长度为n的序列x, q个询问: 某区间内的最大连续子段和, 求和时相同的数只计算一次, 定义空段的和为0. (1≤n,q≤10^5, 序列中的元素是[-105,105]上的整数) 听说是一道不错的线段树, 就去做了一下. 类似的处理方法学习过, 转化后的新问题也做过, 可还是没能完全自己搞出来......TAT
动态最大连续子段和有一个经典的做法: 线段树维护区间和, 最大前缀和, 最大后缀和, 最大连续子段和. 本题由于相同的数只计算一次, 无法直接合并左子区间的最大后缀和, 右子区间的最大前缀和.
令一个连续子段内相同的数仅在第一次出现时计算. 设pre[i]为x[i]上一次出现的位置, 如果不存在则pre[i]=0. 那么, x[i]仅在这些[l,r]中被计算:
pre[i] < l <= i
i <= r <= n把一个区间看成二维平面上的点, 左端点作横坐标, 右端点作纵坐标. 每个x[i]使一个矩形中的点权增加一个值. 令x>y的点(x,y)的权值为0, 则查询转化为询问某矩形中最大点权.
两道思路类似的题: - [bzoj 4540] [Hnoi2016]序列 - [bzoj 4826] [Hnoi2017]影魔
不妨对x轴建线段树, 将询问按右端点排序, 向y轴正方向扫描. 那么, 线段树需要支持区间加, 查询某一时段的历史最大值. 可是这样只能求出前缀和, 而历史最大值不满足区间减法 (广义上的).
瞥了一眼题解, 似乎就是这么做的? 又画了画图: 
绿色部分是真正要查询的. 蓝色部分只要赋成0, 对查询结果是没有影响的. 所以, 待查的就是区间历史最大值的前缀和.
一个看起来很一般的问题难以解决, 那就考虑一下题目中的需求是否具有某种特殊性.
线段树要同时支持区间加和区间历史最值查询用懒标记即可实现. 分别对区间最大值和区间历史最大值打标记. 考虑两个操作序列的复合 (+代表一次区间加): ++++ x +++ = +++++++
历史最大值要么不变, 要么等于当前最大值加上上述操作序列的某个前缀.
见[bzoj 3064] Tyvj 1518 CPU监控: 线段树的Lazy tag
看以前写的东西挺有意思的~
#define ALL 1, 1, n
const int N = 1e5;
struct Seg {
int v[N*4], d[N*4], h[N*4], dh[N*4];
void down(int o, int _d, int _dh)
{
h[o] = max(h[o], v[o] + _dh);
dh[o] = max(dh[o], d[o] + _dh);
d[o] += _d;
v[o] += _d;
}
void down(int o)
{
if (d[o] || dh[o]) {
down(o*2, d[o], dh[o]);
down(o*2+1, d[o], dh[o]);
d[o] = dh[o] = 0;
}
}
void up(int o)
{
v[o] = max(v[o*2], v[o*2+1]);
h[o] = max(h[o*2], h[o*2+1]);
}
void add(int L, int R, int a, int o, int l, int r)
{
if (L <= l && r <= R) return down(o, a, a), void();
down(o);
int m = (l+r)/2;
if (L <= m) add(L, R, a, o*2, l, m);
if (R > m) add(L, R, a, o*2+1, m+1, r);
up(o);
}
int query(int L, int R, int o, int l, int r)
{
if (L <= l && r <= R) return h[o];
down(o);
int m = (l+r)/2, ans = 0;
if (L <= m) ans = query(L, R, o*2, l, m);
if (R > m) ans = max(ans, query(L, R, o*2+1, m+1, r));
return ans;
}
} T;
struct Query {
int l, r, k;
bool operator<(const Query& o) const
{
return r < o.r;
}
} Q[N];
int x[N+1], id[2*N+1], pre[N+1], ans[N];
int main()
{
int n;
scanf("%d", &n);
rep (i, 1, n+1) {
scanf("%d", x+i);
pre[i] = id[x[i]+N];
id[x[i]+N] = i;
}
int q;
scanf("%d", &q);
rep (i, 0, q) {
scanf("%d%d", &Q[i].l, &Q[i].r);
Q[i].k = i;
}
sort(Q, Q+q);
int j = 1;
rep (i, 0, q) {
while (j <= Q[i].r) {
T.add(pre[j]+1, j, x[j], ALL);
++j;
}
ans[Q[i].k] = T.query(Q[i].l, Q[i].r, ALL);
}
rep (i, 0, q)
printf("%d\n", ans[i]);
return 0;
}