解题报告：P8348 环路运输

题意

给定一个有 $n$ 个点的环（$1 \le n \le 1 \times 10 ^ 6$），环上每个点有一个权值 $v_i$，环上每条边的长度均为 $1$，求 $\max \limits_{1 \le i, j \le n} \lbrace v_i + v_j + dis(i, j) \rbrace$

思路

首先断环为链，将原序列复制一次到原序列后边

我们设 $f_i$ 表示 $\max \limits_{1 \le j \le n} \lbrace v_i + v_j + dis(i, j) \rbrace$

由于是一个环，$dis(i, j)$ 表示的是 $i, j$ 之间的最短距离，也就是说 $dis(i, j) = \min \lbrace |i - j|, |n - (i - j)| \rbrace$

所以一定有 $dis(i, j) \le \left\lfloor \frac{n}{2} \right\rfloor$

为了绕过这个限制，我们可以钦定 $f_i$ 中 $(i, j)$ 的顺时针距离不超过 $\left\lfloor \frac{n}{2} \right\rfloor$

在这个含意下，由于我们已经将原序列复制了一次，并不会对答案造成影响（感性理解一下）

那么新的含意下， $f_i = \max \limits_{i - \left\lfloor \frac{n}{2} \right\rfloor \le j < i} \lbrace v_i + v_j + i - j\rbrace$

那么考虑如何 $O(1)$ 求出 $f_i$

首先我们可以对 $f_i$ 进行如下变换：

$$\begin{aligned} f_i & = \max \limits_{i - \left\lfloor \frac{n}{2} \right\rfloor \le j < i} \lbrace v_i + v_j + i - j\rbrace \\ & = \max \limits_{i - \left\lfloor \frac{n}{2} \right\rfloor \le j < i} \lbrace v_j - j\rbrace + v_i + i \\ \end{aligned}$$

那么现在问题就变成了如何 $O(1)$ 快速求出 $\max \limits_{i - \left\lfloor \frac{n}{2} \right\rfloor \le j < i} \lbrace v_j - j \rbrace$

显然，可以贡献到 $f_i$ 的 $j$ 是不断变化的，但是一直有 $i - \left\lfloor \frac{n}{2} \right\rfloor \le j < i$

这个区间可以看作是一个滑动窗口，那么我们要求的即为滑动窗口中的最小值

我们维护可以一个单调（双端）队列，队列中存的值为 $v_i - i$，且从头到尾单调递减

我们从头到尾遍历序列中的每个位置，进行如下操作：

1. 把队列头部所有不满足 $i - \left\lfloor \frac{n}{2} \right\rfloor \le j < i$ 的 $j$ 弹出队列
2. 使用队首更新答案
3. 将所有在队尾且小于 $v_i - i$ 或 $i - \left\lfloor \frac{n}{2} \right\rfloor \le j < i$ 的 $j$ 弹出队列
4. 将 $v_i - i$ 插入队尾

这样我们就求出了滑动窗口最值，同时也就求出了答案

代码

#include <bits/stdc++.h>
namespace solution
{
    typedef long long LL;
    const int MAXN = 2e6 + 5;
    int n;
    LL ans = 0;
    LL v[MAXN];
    std::deque<std::pair<LL, int>> q;
    int main()
    {
        scanf("%d", &n);
        for (int i = 1; i <= n; i++)
        {
            scanf("%lld", &v[i]);
            v[i + n] = v[i];
        }
        for (int i = 1; i <= 2 * n; i++)
        {
            while (!q.empty() && q.front().second < i - n / 2)
            {
                q.pop_front();
            }
            if (!q.empty())
            {
                ans = std::max(ans, v[i] + q.front().first + i);
            }
            while (!q.empty() && (q.back().first < v[i] - i || q.back().second < i - n / 2))
            {
                q.pop_back();
            }
            q.push_back(std::make_pair(v[i] - i, i));
        }
        printf("%lld\n", ans);
        return 0;
    }
}
int main()
{
    solution::main();
    return 0;
}