[离线] [线段树] GSS2

_Cheems · 2024-01-29 07:49:35 · 个人记录

套路：区间去重相关问题离线处理。

考虑将序列元素 a_i 逐个加入，并在加入后处理以 i 为右端点的询问。

记 s_j 为当前 [j,i] 区间内的不重复元素之和，考虑维护这个东东。

记 pre_i 为上一个与 a_i 相等的元素之下标，那么加入 a_i 便会使 [pre_i+1,i] 内的 s+=a_i。

考虑查询，不难发现左端点固定后，记 s_j 的历史最大值为 hs_j，它等价于 [j,k],j\le k\le i 的最大值。

那么 [l,i] 内连续子段的最大值便是 hs_j,l\le j \le i 的最大值。

考虑维护 hs，用一棵支持区间加和区间历史最大值的线段树即可。

具体实现，除 s,hs 外，还需维护 tag，结束了么？

考虑下传标记时重复标记的处理，显然（并不显然）不能直接相加，因为 son_u 上的标记还没来得及下传，假如 tag_u 是负数就寄了。

因此需维护 htag，表示当前节点 tag 的历史最大值，问题解决。

代码

#include<bits/stdc++.h>
using namespace std;

#define int long long
const int N = 1e6 + 5, NC = 1e5;
int n, q, a[N], l, r, inf, pre[N << 1], f[N << 1], ans[N];
vector<pair<int, int> > ask[N];

namespace Sg_Tree{
    #define lt (u << 1)
    #define rt (u << 1 | 1)
    #define mid (l + r >> 1)
    int s[N << 2], hs[N << 2], tag[N << 2], htag[N << 2];

    inline void psup(int u) {s[u] = max(s[lt], s[rt]); hs[u] = max(hs[u], s[u]);}
    inline void psdw(int u){
        htag[lt] = max(htag[lt], tag[lt] + htag[u]);
        htag[rt] = max(htag[rt], tag[rt] + htag[u]);
        tag[lt] += tag[u], tag[rt] += tag[u]; 
        hs[lt] = max(hs[lt], s[lt] + htag[u]);
        hs[rt] = max(hs[rt], s[rt] + htag[u]);
        s[lt] += tag[u], s[rt] += tag[u];
        htag[u] = tag[u] = 0;
    }
    inline void upd(int u, int l, int r, int ll, int rr, int k){
        if(ll <= l && r <= rr){
            tag[u] += k, htag[u] = max(htag[u], tag[u]);
            s[u] += k, hs[u] = max(hs[u], s[u]); 
            return ;
        }
        psdw(u);
        if(ll <= mid) upd(lt, l, mid, ll, rr, k);
        if(rr > mid) upd(rt, mid + 1, r, ll, rr, k);
        psup(u);
    }
    inline int fid(int u, int l, int r, int ll, int rr){
        if(ll <= l && r <= rr) return hs[u];
        psdw(u); int res = inf;
        if(ll <= mid) res = fid(lt, l, mid, ll, rr);
        if(rr > mid) res = max(res, fid(rt, mid + 1, r, ll, rr));
        psup(u);
        return res; 
    }   
}
using namespace Sg_Tree;
signed main(){
    cin >> n;
    for(int i = 1; i <= n; ++i){
        scanf("%lld", &a[i]);
        pre[i] = f[a[i] + NC], f[a[i] + NC] = i;
    }
    cin >> q;
    for(int i = 1; i <= q; ++i) scanf("%lld%lld", &l, &r), ask[r].push_back({l, i});
    for(int i = 1; i <= n; ++i){
        upd(1, 1, n, pre[i] + 1, i, a[i]);
        for(auto P : ask[i])
            ans[P.second] = fid(1, 1, n, P.first, i);
    }
    for(int i = 1; i <= q; ++i) printf("%lld\n", max(0ll, ans[i]));
    return 0;
}