SP1557 GSS2 - Can you answer these queries II 题解

题目链接：SP1557 GSS2 - Can you answer these queries II

题意：

给定一个长度为 $n$ 的序列 $a_i$ 。

$q$ 次询问，查询区间最大子段和，相同的数只算一次。选出的子段可以为空

数据范围：

$1\le n,q \le 10^5,~ |a_i| \le 10^5$ 。

~~真就加了一句话就比 GSS1 难了 $+\infty$ 倍（悲）~~ 感觉这题是 GSS 系列第二难的题。

因为相同的数只能算一次，所以直接维护那 $4$ 个信息就不太行了。

想起来一道题叫 HH 的项链，这题的思想和那道题有一些相似。

考虑从左往右依次加入每个元素，记 $\mathtt{pre}(a_i)$ 表示 $a_i$ 上次出现的位置。

对于第 $i$ 个元素 $a_i$ ，它能产生贡献的范围为 $[\,\mathtt{pre}(a_i) + 1, i-1\,]$

任意 $l~(\mathtt{pre}(a_i) < l < i-1)$ ，我们把 $a_i$ 拼接上去，形成 $[l, i]$ 的串

注意到这是一个类似“区间拼接”的操作，不妨用线段树维护为区间加法的形式

具体地，线段树叶子结点 $u$ 表示以 $u$ 为起点的最大子串长。

一次区间加法可能让结点的值变大，也可能变小，因此我们需要维护一个历史最大值。

考虑离线处理询问。对于询问 $(j,i)$ ，我们在加入 $a_i$ 后立即查询 $j \le l \le r \le i$ 的历史最大值。

注意到如果 $l$ 固定时， $[l,r]$ 的历史最大值其实就是 $l$ 贡献的最大值，因为历史最大值是单调不降的。

因此 $l$ 固定时，直接选 $r=i$ 即可，则 $r$ 固定了，又可知 $l$ 越小，越可能产生大的贡献。

则询问其实就是 $[j,i]$ 的历史最大值（注意在 $a_i$ 加入后才能查询）

考虑维护历史最大值。具体可以参考洛谷P5568 [SDOI2008] 校门外的区间题解

这里简单讲一下，我们需要维护当前最大值、当前加法标记，历史最大值，历史最大加法标记。

为什么要维护历史最大加法标记呢？因为我们每次的修改是在标记上进行的，

所以下传信息的时候，那个标记不一定是最大的时候，或者说我们会不小心丢失历史的某些信息。

然后这题就没啦，不过这个离线的操作还是比较难想的

时间复杂度 $\mathcal{O}((n + q) \log n)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define DDD cout << "Line here is " << __LINE__ << '\n';
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(1e5+15))
#define M ((int)(2e6+15))
#define B 100000

#define ls(at) ((at) << 1)
#define rs(at) ((at) << 1 | 1)
int n,m,a[N],L[N],R[N],id[N],pre[M];
struct node { int mx1,mx2,tag1,tag2; } tr[N * 4],ans[N];
void push_up(int at)
{
    up(tr[at].mx1 = tr[ls(at)].mx1, tr[rs(at)].mx1);
    up(tr[at].mx2 = tr[ls(at)].mx2, tr[rs(at)].mx2);
}
node merge(node a, node b)
{ return {max(a.mx1, b.mx1), max(a.mx2, b.mx2), 0, 0}; }
void proc(int u, int f)
{
    up(tr[u].mx2, tr[u].mx1 + tr[f].tag2);
    up(tr[u].tag2, tr[u].tag1 + tr[f].tag2);
    tr[u].mx1 += tr[f].tag1;
    tr[u].tag1 += tr[f].tag1;
}
void push_down(int at)
{
    proc(ls(at), at); proc(rs(at), at);
    tr[at].tag1 = tr[at].tag2 = 0;
}
void update(int nl,int nr,int k,int l = 1,int r = n,int at = 1)
{
    if(nl <= l && r <= nr)
    {
        tr[at].mx1 += k; up(tr[at].mx2, tr[at].mx1);
        tr[at].tag1 += k; up(tr[at].tag2, tr[at].tag1);
        return ;
    }
    push_down(at);
    int mid = (l + r) >> 1;
    if(nl <= mid) update(nl,nr,k,l,mid,ls(at));
    if(nr > mid) update(nl,nr,k,mid+1,r,rs(at));
    push_up(at);
    return;
}
node query(int nl,int nr,int l = 1,int r = n,int at = 1)
{
    if(nl <= l && r <= nr) return tr[at];
    push_down(at); int mid = (l + r) >> 1;
    if(nl > mid) return query(nl,nr,mid+1,r,rs(at));
    if(nr <= mid) return query(nl,nr,l,mid,ls(at));
    return merge(query(nl,nr,l,mid,ls(at)), query(nl,nr,mid+1,r,rs(at)));
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n;
    for(int i=1; i<=n; i++) cin >> a[i];
    cin >> m;
    for(int i=1; i<=m; i++) { cin >> L[i] >> R[i]; id[i] = i; }
    sort(id + 1, id + 1 + m, [](int a,int b) { return R[a] < R[b]; });
    int j = 1;
    for(int i=1; i<=n; i++)
    {
        update(pre[a[i] + B] + 1, i, a[i]);
        for(pre[a[i] + B] = i; R[id[j]] == i && j <= m; j++)
            ans[id[j]] = query(L[id[j]], R[id[j]]);
    }
    for(int i=1; i<=m; i++) cout << ans[i].mx2 << '\n';
    return 0;
}