20231107题解

发表于 分类于 ， 阅读次数：

mission

原题： JOI2018 \(\mathcal{Link}\)

首先用 dijkstra 求出从 \(A,B,C,D\) 出发的单源最短路。显然，最优的方案一定是从 \(C\) 出发自己走一段，再在 \(A\to B\) 最短路上连续走一段，再自己走一段到 \(D\)。我们可以枚举进入最短路的点，再枚举离开最短路的点，就得到了 \(\mathcal{O}(n^2)\) 做法。

考虑优化。\(A\) 到 \(B\) 的最短路图应该是一个有向无环图。所以按照拓扑序的顺序依次枚举离开的位置，这样可以从拓扑序较小的点继承最优的进入点，就可以 \(\mathcal{O}(n)\)，类似于 DAG 上的 DP。

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
#include <bits/stdc++.h>
using namespace std;

const int maxn = 2e5 + 5;

template<class T>
void read(T &r) {
    r = 0; char ch = getchar(); bool f = false;
    while (ch < '0' || ch > '9') { if (ch == '-') f ^= 1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { r = r * 10 + ch - '0'; ch = getchar(); }
    if (f) r = -r;
}

struct node {
    int v;
    long long w;
    node() {}
    node(int _v, long long _w) {
        v = _v, w = _w;
    }
    bool operator < (const node &x) const {
        return w < x.w;
    }
    bool operator > (const node &x) const {
        return w > x.w;
    }
};

int n, m, s, t, ss, tt;
vector<node> graph[maxn];
long long dis_s[maxn], dis_t[maxn], dis_ss[maxn], dis_tt[maxn];
long long min_s[maxn], min_t[maxn];

void dijk(int s, long long dis[]) {
    priority_queue<node, vector<node>, greater<node> > pq;
    memset(dis, 0x3f, sizeof dis_s);
    pq.emplace(s, 0);
    while (!pq.empty()) {
        node now = pq.top(); pq.pop();
        if (dis[now.v] != 0x3f3f3f3f3f3f3f3f) continue;
        dis[now.v] = now.w;
        for (node e : graph[now.v]) {
            if (dis[e.v] == 0x3f3f3f3f3f3f3f3f) {
                pq.emplace(e.v, e.w + now.w);
            }
        }
    }
}

int cnt[maxn];

int main() {
    freopen("mission.in", "r", stdin); freopen("mission.out", "w", stdout);
    read(n); read(m); read(s); read(t); read(ss); read(tt);
    for (int i = 1; i <= m; i++) {
        int u, v; long long w;
        read(u); read(v); read(w);
        graph[u].emplace_back(v, w);
        graph[v].emplace_back(u, w);
    }
    dijk(s, dis_s);
    dijk(t, dis_t);
    dijk(ss, dis_ss);
    dijk(tt, dis_tt);
    for (int i = 1; i <= n; i++) {
        if (dis_s[i] + dis_t[i] == dis_s[t]) {
            for (auto e : graph[i]) {
                if (dis_s[i] + dis_t[e.v] + e.w == dis_s[t]) {
                    cnt[e.v]++;
                }
            }
        }
    }
    queue<int> q;
    for (int i = 1; i <= n; i++) {
        if (dis_s[i] + dis_t[i] == dis_s[t]) {
            if (!cnt[i]) q.emplace(i);
        }
    }
    vector<int> turn;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        turn.emplace_back(u);
        for (auto e : graph[u]) {
            if (dis_s[u] + e.w + dis_t[e.v] == dis_s[t]) {
                if (!(--cnt[e.v])) {
                    q.emplace(e.v);
                }
            }
        }
    }
    memset(min_s, 0x3f, sizeof min_s);
    memset(min_t, 0x3f, sizeof min_t);
    for (int u : turn) {
        min_s[u] = dis_tt[u];
        for (auto e : graph[u]) {
            if (dis_s[e.v] + e.w + dis_t[u] == dis_s[t]) {
                min_s[u] = min(min_s[u], min_s[e.v]);
            }
        }
    }
    reverse(turn.begin(), turn.end());
    for (int u : turn) {
        min_t[u] = dis_tt[u];
        for (auto e : graph[u]) {
            if (dis_s[u] + e.w + dis_t[e.v] == dis_s[t]) {
                min_t[u] = min(min_t[u], min_t[e.v]);
            }
        }
    }
    long long ans = dis_ss[tt];
    for (int i = 1; i <= n; i++) {
        if (dis_s[i] + dis_t[i] == dis_s[t]) {
            ans = min(ans, dis_ss[i] + min(min_s[i], min_t[i]));
        }
    }
    printf("%lld\n", ans);
    return 0;
}

subarray

包含 \(i\) 的最大子段和就是以 \(i\) 结尾的最大子段和加上以 \(i\) 开头的最大子段和再减去 \(i\) 的值。

我们只考虑求以 \(i\) 开头的最大子段和。

考虑前缀和数组 \(pre\)，最大子段和就是 \(\mathcal{O}(\max_{j=i}^n{pre_j} - pre_i)\)。可以考虑用线段树做区间加等差数列，区间求最值，据说复杂度是 \(\mathcal{O}(m\log^2n)\)。

考虑离线。如果全局加了 \(w\)，则每个点的实际值是 \(pre_i + wi\)。由于我们要求的是后缀最小值，所以有类似于单调栈上的性质：如果一个点比你靠后还比你大，那它一定更优。我们可以建出单调栈，然后在单调栈上二分，找到第一个大于等于 \(i\) 的位置即可。

容易发现，如果 \(w\) 从小到大增加，则单调栈内部的元素只减不增。我们考虑求出每个点最多在单调栈里待到什么时候为止，记为 \(w_i\)。

先考虑暴力：对于 \(j > i\)，当 \(w > \frac{pre_i - pre_j}{j - i}\) 的时候，\(j\) 就能够把 \(i\) 赶出单调栈。所以 \(w_i=\min{\lfloor \frac{pre_i - pre_j}{j - i} \rfloor}\)。

怎么优化呢？我们将 \((i, pre_i)\) 看成平面上的点，则要求的东西就是最小的负斜率。如果我们维护一个斜率的单调栈，就可以 \(\mathcal{O}(n)\) 求出。

具体来说，如果 \((i, pre_i)\) 与 \((j, pre_j)\) 的所连直线高于点 \((k, pre_k)\)（其中 \(i<k<j\)），则当有一个更小的 \(l\) 时，无论 \((l, pre_l)\) 在直线的哪一侧，它与 \(i\) 和 \(j\) 的连线斜率中都一定有一个比 \(k\) 更优。则 \(k\) 就可以出栈了。栈内元素保持斜率的单调降。

在上图中，无论是直线下方的 \((l, pre_l)\) 还是上方的 \((l, pre_l')\)，都不会与被覆盖的 \(k\) 产生贡献（蓝线），而是与 \(i\) 和 \(j\) 产生贡献（红线）。另外，斜率的单调栈内存了黄色的线段。

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
#include <algorithm>
#include <bits/stdc++.h>
#include <climits>
using namespace std;

template <class T>
void read(T &r) {
    r = 0; int ch = getchar(), f = 0;
    while (!isdigit(ch)) { if (ch == 45) f ^= 1; ch = getchar(); }
    while (isdigit(ch)) (r *= 10) += ch - 48, ch = getchar();
    if (f) r = -r;
}

const int maxn = 2e5 + 5;
int n, m;
long long a[maxn], pre[maxn], suf[maxn];
int id[maxn], tmp_id[maxn];
long long ans_pre[maxn], ans_suf[maxn], ans[maxn];
set<int> st;

struct node { long long w; int x, id; node() {} node(long long w, int x, int id): w(w), x(x), id(id) {}};
vector<node> q;
vector<int> que;

int main() {
    freopen("subarray.in", "r", stdin);
    freopen("subarray.out", "w", stdout);
    read(n); read(m);
    // if (n > 2000) return 0;
    for (int i = 1; i <= n; i++) read(a[i]);
    for (int i = 1; i <= n; i++) pre[i] = pre[i - 1] + a[i];
    for (int i = n; i >= 1; i--) suf[i] = suf[i + 1] + a[i];

    ans_pre[n] = 2e12 + 1;
    que.emplace_bac独角兽k(n);
    for (int i = n - 1; i >= 1; i--) {
        while (que.size() > 1 && (pre[que.back()] - pre[i]) * (que[que.size() - 2] - que.back())
                               < (pre[que[que.size() - 2]] - pre[que.back()]) * (que.back() - i)) que.pop_back();
        ans_pre[i] = (pre[que.back()] > pre[i]) ? -(pre[que.back()] - pre[i] - 1) / (que.back() - i) - 1 : (pre[i] - pre[que.back()]) / (que.back() - i);
        que.emplace_back(i);
    }
    ans_suf[1] = 2e12 + 1;
    que.clear(); que.emplace_back(1);
    for (int i = 2; i <= n; i++) {
        while (que.size() > 1 && (suf[que.back()] - suf[i]) * (que.back() - que[que.size() - 2])
                               < (suf[que[que.size() - 2]] - suf[que.back()]) * (i - que.back())) que.pop_back();
        ans_suf[i] = (suf[que.back()] > suf[i]) ? -(suf[que.back()] - suf[i] - 1) / (i - que.back()) - 1 : (suf[i] - suf[que.back()]) / (i - que.back());
        que.emplace_back(i);
    }

    long long sum = 0;
    for (int i = 1; i <= m; i++) {
        int op, x;
        read(op); read(x);
        if (op == 1) {
            q.emplace_back(sum, x, q.size() + 1);
            ans[q.size()] = a[x] + sum;
        }
        else sum += x;
    }
    sort(q.begin(), q.end(), [](node &a, node &b) -> bool { return a.w < b.w; });
    
    for (int i = 1; i <= n; i++) id[i] = i, st.insert(i);
    sort(id + 1, id + n + 1, [](int a, int b) -> bool { return ans_pre[a] < ans_pre[b]; });
    int j = 1;
    for (auto x : q) {
        while (j <= n && ans_pre[id[j]] < x.w) st.erase(id[j++]);
        int p = *st.lower_bound(x.x);
        ans[x.id] += pre[p] - pre[x.x] + (p - x.x) * x.w;
    }
    
    st.clear();
    for (int i = 1; i <= n; i++) id[i] = i, st.insert(i);
    sort(id + 1, id + n + 1, [](int a, int b) -> bool { return ans_suf[a] < ans_suf[b]; });
    j = 1;
    for (auto x : q) {
        while (j <= n && ans_suf[id[j]] < x.w) st.erase(id[j++]);
        int p = *prev(st.upper_bound(x.x));
        ans[x.id] += suf[p] - suf[x.x] + (x.x - p) * x.w;
    }
    for (int i = 1; i <= q.size(); i++) {
        printf("%lld\n", ans[i]);
    }
    return 0;
}