SP1557 GSS2 - Can you answer these queries II【线段树】

题意

给出 $n$ 个数，$q$ 次询问，求询问区间的最大子段和，相同的数只算一次。
题目链接

思路

询问区间最大子段和是线段树的经典操作，通过维护每个区间包括左端点的最大子段和和包括右端点的最大子段和可以轻松的实现。
但是此题有一个限制，相同的数只能算一次，于是，无法使用原先简单的维护方法。
令$mx[i,j]$表示以$i$为区间左端点，区间右端点从$i$到$j$时所有区间的和（不算重复元素的和）的最大值。考虑区间$[l,r]$中的所有子段，最大子段和可以转化为 m a x i { m x [ i , r ] } ( l ≤ i ≤ r ) max_i\{mx[i, r]\}(l \le i \le r) maxi​{mx[i,r]}(l≤i≤r)。考虑$mx[i,r]$如何计算，其实相当于是$[l,r]$区间中本质不同元素累加期间的最大值（也称为历史最大值），于是问题就转化为了维护$[l,r]$区间历史最大值的最大值。维护的方法参考这一题洛谷P4314。。
通常，相同的数只算一次的问题可以考虑采取离线操作。我们将所有询问离线并按照右端点升序排序。
考虑我们处理到了第$i$个位置，假设$a[i]$在之前出现的位置为$pre[i]$，那么将区间$[pre[i]+1,i]$加上$a[i]$（区间加法）即可。

代码

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

const int N = 100005;

int a[N], pre[N];
int pos[N * 2];
LL ans[N];
struct TreeNode
{
    int l, r;
    LL mx, mx_his;
    LL addlz, add_his;
}t[N << 2];
struct Query
{
    int l, r, id;
    bool operator < (const Query& b) const 
    {
        return r < b.r;
    }
}q[N];

void push_up(int i)
{
    t[i].mx = max(t[i << 1].mx, t[i << 1 | 1].mx);
    t[i].mx_his = max(t[i << 1].mx_his, t[i << 1 | 1].mx_his);
}

void Add(int i, LL add, LL his_add)
{
    t[i].add_his = max(t[i].add_his, t[i].addlz + his_add);
    t[i].mx_his = max(t[i].mx_his, t[i].mx + his_add);
    t[i].mx += add;
    t[i].addlz += add;
}

void push_down(int i)
{
    Add(i << 1, t[i].addlz, t[i].add_his);
    Add(i << 1 | 1, t[i].addlz, t[i].add_his);
    t[i].add_his = t[i].addlz = 0;
}

void build(int i, int l, int r)
{
    t[i].l = l, t[i].r = r;
    if (l == r) return;
    int mid = (l + r) >> 1;
    build(i << 1, l, mid);
    build(i << 1 | 1, mid + 1, r);
    push_up(i);
}

void update(int i, int l, int r, LL k)
{
    if (l <= t[i].l && t[i].r <= r)
    {
        Add(i, k, k);
        return;
    }
    push_down(i);
    int mid = (t[i].l + t[i].r) >> 1;
    if (l <= mid) update(i << 1, l, r, k);
    if (r > mid) update(i << 1 | 1, l, r, k);
    push_up(i);
}

LL query(int i, int l, int r)
{
    if (l <= t[i].l && t[i].r <= r) return t[i].mx_his;
    push_down(i);
    int mid = (t[i].l + t[i].r) >> 1;
    LL mx = -1e18;
    if (l <= mid) mx = max(mx, query(i << 1, l, r));
    if (r > mid) mx = max(mx, query(i << 1 | 1, l, r));
    return mx;
}

int main()
{
    #ifdef ZYCMH
    freopen("1.in", "r", stdin);
    freopen("1.out", "w", stdout);
    #endif
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++ )
        scanf("%d", &a[i]);
    build(1, 1, n);
    
    for (int i = 1; i <= n; i ++ )
    {
        pre[i] = pos[a[i] + 100000];
        pos[a[i] + 100000] = i;
    }

    int m;
    scanf("%d", &m);
    for (int i = 1; i <= m; i ++ )
    {
        scanf("%d%d", &q[i].l, &q[i].r);
        q[i].id = i;
    }

    sort(q + 1, q + 1 + m);

    int cur = 1;
    for (int i = 1; i <= n; i ++ )
    {
        update(1, pre[i] + 1, i, a[i]);
        while(cur <= m && q[cur].r <= i)
            ans[q[cur].id] = query(1, q[cur].l, q[cur].r), cur ++;
    }

    for (int i = 1; i <= m; i ++ )
        printf("%lld\n", ans[i]);

    return 0;
}

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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133