原题呈现

我爱喝奶茶#

题目背景#

小信家附近开了一家奶茶店，从此他迷上了喝奶茶．

题目描述#

奶茶店共有 $m$ 款特色限定奶茶，编号为 $1,2,...,m$ ，第 $i$ 款奶茶给小信带来的愉悦度为 $w_i$ ．

在 $n$ 天之中，奶茶店每天只会上架其中一款限定奶茶，第 $i$ 天上架的是第 $f_i$ 款．

小信可以选择打卡连续的 $[l,r]$ 天内上架的所有奶茶．

但是小信是一个非常喜新厌旧的人，一旦同一款奶茶打卡多于一次，就会厌恶这款奶茶，甚至忘记奶茶曾经带给他的快乐（即仅当该款奶茶在区间内恰好只打卡过 1 次时，才能获得其愉悦程度 $w_i$ ）．

现在，请问小信怎么打卡能让他的愉悦程度最大，最大的愉悦度是多少．

输入格式#

第一行两个整数 $n,m$ ．

第二行包含 $n$ 个整数，第 $i$ 个表示 $f_i$ ．

第三行包含 $m$ 个整数，第 $i$ 个表示 $w_i$ ．

输出格式#

一行三个整数，分别表示打卡的区间 $[l,r]$ ，以及最大打卡收益，用空格隔开．如果有多个区间满足条件，输出区间长度最短且 $l$ 最小的一个．

样例#

样例输入#

1
9 4
2
2 3 1 1 4 1 2 4 1
3
5 3 6 6

样例输出#

1
1 5 15

数据范围#

对于 $20\text{pts}$ 的数据： $0 \le n,m \le 500$

对于 $60\text{pts}$ 的数据： $0 \le n,m \le 10^4$ 其中有 $10\text{pts}$ 的数据满足每种奶茶最多出现两次

对于 $100\text{pts}$ 的数据： $0 \le n,m \le 10^6$ ， $1 \le f_i \le m$ ， $1 \le w_i \le 10^9$

我们枚举起点，对于每一个起点 $i$ ，对从第 $i$ 天起的每一天的奶茶的权值做一次前缀和，其中，第二次出现的奶茶权值为 $-w[i]$ ，第三次出现的奶茶权值为 $0$ ．

如下面的例子：

1
9 4
2
2 3 1 1 4 1 2 4 1
3
1 2 3 4

则以第一天为起点每一天出现的奶茶的权值列表为：

1
2 3 1 1 4 1 2 4 1

将其中第二次出现的奶茶权值置为 $-w[i]$ ，第三次出现的奶茶权值置为 $0$ ，则可得：

1
2 3 1 -1 4 0 -2 -4 0

将其做一次前缀和：

1
2 5 6 5 9 9 7 3 3

前缀和数组中最大的值（设其下标为 $k$ ，此例中 $k=5$ ）即为起点为 1 时的最大答案，区间为 $[1,k]$ ．

再如，第二天为起点每一天出现的奶茶的权值列表为：

1
3 1 1 4 1 2 4 1

将其中第二次出现的奶茶权值置为 $-w[i]$ ，第三次出现的奶茶权值置为 $0$ ，则可得：

1
3 1 -1 4 0 2 -4 0

将其做一次前缀和：

1
3 4 3 7 7 9 5 5

前缀和数组中最大的值（设其下标为 $k$ ，此例中 $k=6$ ）即为起点为 2 时的最大答案，区间为 $[2,k]$ ．

对于每一天作为起点都这么操作一次，取起点为 $[1,n]$ 答案的最大值，时间复杂度为 $O(n^2)$ ，考虑优化．

枚举起点好像没有优化空间，但是如何快速处理前缀和呢？

仔细观察原数组在 $i\rightarrow i+1$ 时有什么变化：

原数组中第一个奶茶种类为 a[i] 的奶茶（设其下标为 $i$ ）消失了．
原数组中第二个奶茶种类为 a[i] 的奶茶（设其下标为 $nxt_i$ ）权值取了相反数，变为 w[a[i]]．
原数组中第三个奶茶种类为 a[i] 的奶茶（设其下标为 $nxt_{nxt_i}$ ）权值从 0 变为 -w[a[i]]．

对应到前缀和数组（设大小为 $n$ ）上就是：

区间 $[i,n]$ 中每一项减少 w[a[i]]．
区间 $[nxt_i, n]$ 中每一项增加 2*w[a[i]]．
区间 $[nxt_{nxt_i}, n]$ 中每一项减少 w[a[i]]．

区间修改使用线段树优化，就可以在 $O(\log n)$ 的复杂度内更新前缀和数组．

至于区间，只需要在线段树上二分查找：

对于每一个线段树上的节点，比较其两个子节点的 max 哪一个更大，选择更大的那个节点，在该子节点中继续查找，直到找到大小为 1 的节点．

标程

1
#include <bits/stdc++.h>
2
typedef long long ll;
3
using namespace std;
4
const int N = 1e6 + 100;
5

6
int n, m, a[N], w[N], l, r;
7
ll s[N];
8
ll ans = -1;
9

10
vector<int> vec[N];
11
int pointer[N];
12

13
class SegmentTree {
14
  public:
15
    struct Node {
16
        int l, r;
17
        ll max;
18
        ll add;
19
    } f[N * 5];
20
    void Build(int t, int l, int r) {
21
        f[t].l = l;
22
        f[t].r = r;
23
        if (l == r) {
24
            f[t].max = s[l];
25
            return;
26
        }
27

28
        int mid = (l + r) / 2;
29
        Build(t * 2, l, mid);
30
        Build(t * 2 + 1, mid + 1, r);
31

32
        pushup(t);
33
    }
34
    void Add(int t, int x, int y, ll v) {
35
        pushdown(t);
36
        if (x <= f[t].l && f[t].r <= y) {
37
            f[t].add += v;
38
            f[t].max += v;
39
            return;
40
        }
41
        if (x > f[t].r || y < f[t].l) {
42
            return;
43
        }
44

45
        Add(t * 2, x, y, v);
46
        Add(t * 2 + 1, x, y, v);
47

48
        pushup(t);
49
    }
50
    ll Query(int t, int x, int y) {
51
        pushdown(t);
52

53
        if (x <= f[t].l && f[t].r <= y) {
54
            return f[t].max;
55
        }
56
        if (x > f[t].r || y < f[t].l) {
57
            return -1;
58
        }
59

60
        return max(Query(t * 2, x, y), Query(t * 2 + 1, x, y));
61
    }
62
    int findmax(int t) {
63
        if (f[t].l == f[t].r) {
64
            return f[t].l;
65
        }
66
        if (Query(t * 2, 1, n) >= Query(t * 2 + 1, 1, n)) {
67
            return findmax(t * 2);
68
        }
69
        return findmax(t * 2 + 1);
70
    }
71

72
  private:
73
    void pushup(int t) { f[t].max = max(f[t * 2].max, f[t * 2 + 1].max); }
74
    void pushdown(int t) {
75
        if (f[t].add) {
76
            ll add = f[t].add;
77
            f[t * 2].add += add;
78
            f[t * 2].max += add;
79
            f[t * 2 + 1].add += add;
80
            f[t * 2 + 1].max += add;
81
            f[t].add = 0;
82
        }
83
    }
84
} tr;
85

86
signed main() {
87
    ios::sync_with_stdio(false);
88
    cin.tie(0);
89
    cout.tie(0);
90
    cin >> n >> m;
91
    for (int i = 1; i <= n; i++) {
92
        cin >> a[i];
93
    }
94
    for (int i = 1; i <= m; i++) {
95
        cin >> w[i];
96
    }
97
    for (int i = 1; i <= n; i++) {
98
        vec[a[i]].push_back(i);
99
        int wt = w[a[i]];
100
        if (vec[a[i]].size() == 2) {
101
            wt = -w[a[i]];
102
        }
103
        if (vec[a[i]].size() > 2) {
104
            wt = 0;
105
        }
106
        s[i] = s[i - 1] + wt;
107
    }
108
    tr.Build(1, 1, n);
109
    for (int i = 1; i <= n; i++) {
110
        ll tot = tr.Query(1, 1, n);
111
        int newR = tr.findmax(1);
112
        int nowLen = newR - i + 1;
113
        int miniLen = r - l + 1;
114
        if (tot > ans || (tot == ans && nowLen < miniLen)) {
115
            ans = tot;
116
            l = i;
117
            r = newR;
118
        }
119

120
        int wt = w[a[i]];
121
        tr.Add(1, i, n, -wt);
122
        pointer[a[i]]++;
123
        if (pointer[a[i]] != vec[a[i]].size()) {
124
            int top = vec[a[i]][pointer[a[i]]];
125
            tr.Add(1, top, n, 2ll * wt);
126
            pointer[a[i]]++;
127
            if (pointer[a[i]] != vec[a[i]].size()) {
128
                int top = vec[a[i]][pointer[a[i]]];
129
                tr.Add(1, top, n, -wt);
130
            }
131
            pointer[a[i]]--;
132
        }
133
    }
134
    cout << l << " " << r << " " << ans;
135
    return 0;
136
}

音乐

音乐

我爱喝奶茶#

题目背景#

题目描述#

输入格式#

输出格式#

样例#

样例输入#

样例输出#

数据范围#

文章分享

音乐

安吉D10-T3

我爱喝奶茶#

题目背景#

题目描述#

输入格式#

输出格式#

样例#

样例输入#

样例输出#

数据范围#

文章分享