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;
}