DDOSvoid's Blog

Spoj 1557 GSS2 - Can you answer these queries II

发表于 分类于
本文字数： 1.9k 阅读时长 ≈ 2 分钟

题目描述

https://www.luogu.com.cn/problem/SP1557

简要题意：给定一个长度为 $n$ 的序列，现在有 $m$ 次询问，每次询问区间 $[l,r]$ 的最大子段和，但是需要注意这个最大子段和相同的数只算一次

$n,m\le 10^5$

Solution

我们考虑离线之后扫描线，线段树上每个点维护这个点到当前右端点区间和和历史最大值，容易发现，我们只需要记录 $pre_i$，然后每次更新 $[pre_i+1,i]$ 即可

时间复杂度 $O(n\log n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include <iostream>
#include <map>
#include <vector>
#define maxn 1000010
#define ll long long
using namespace std;

int n, m, a[maxn], pre[maxn];
map<int, int> mp;

#define lc i << 1
#define rc i << 1 | 1
struct Seg {
    ll mx, tmx, add, tadd;
} T[maxn * 4]; 
inline void maintain(int i) {
    T[i].mx = max(T[lc].mx, T[rc].mx);
    T[i].tmx = max(T[lc].tmx, T[rc].tmx); 
}

inline void Update(int i, ll add, ll tadd) {
    T[i].tmx = max(T[i].tmx, T[i].mx + tadd);
    T[i].mx += add;
    T[i].tadd = max(T[i].tadd, T[i].add + tadd);
    T[i].add += add;
}

inline void pushdown(int i) {
    ll &add = T[i].add, &tadd = T[i].tadd;
    Update(lc, add, tadd); Update(rc, add, tadd);
    add = tadd = 0; 
}

void update(int i, int l, int r, int L, int R, int v) {
    if (l > R || r < L) return ;
    if (L <= l && r <= R) return Update(i, v, v);
    int m = l + r >> 1; pushdown(i);
    update(lc, l, m, L, R, v); update(rc, m + 1, r, L, R, v);
    maintain(i); 
}

ll query(int i, int l, int r, int L, int R) {
    if (l > R || r < L) return 0;
    if (L <= l && r <= R) return T[i].tmx;
    int m = l + r >> 1; pushdown(i); 
    return max(query(lc, l, m, L, R), query(rc, m + 1, r, L, R));
}

vector<pair<int, int>> A[maxn];
ll ans[maxn];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        pre[i] = mp[a[i]];
        mp[a[i]] = i; 
    } cin >> m;
    for (int i = 1; i <= m; ++i) {
        int x, y; cin >> x >> y;
        A[y].emplace_back(x, i);
    }
    for (int i = 1; i <= n; ++i) {
        update(1, 1, n, pre[i] + 1, i, a[i]); 
        for (auto [k, id] : A[i]) ans[id] = query(1, 1, n, k, i); 
    }
    for (int i = 1; i <= m; ++i) cout << ans[i] << "\n";
    return 0;
}