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
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
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;
}