「CH 5501」环路运输 (单调队列 + 断环成链)

CH 5501
题意：给定$n$长数列$a$，找出最大的$a_i+a_j+min(|i-j|, n - |i-j|)$ updated on 2019.02.20

$min(|i-j|, n - |i-j|)$也就是逆时针或顺时针从 $i$ 到 $j$ 中较近的一种。
所以我们将环断开成一条链，然后在链上就不用讨论$\min$。

假设$i \leq j$
则对于原串上$i - j \leq \frac n2$，则$n - (i-j) > i - j$，可以对应于复制串上$i,j$之间传物品
对于原串上$i - j \geq \frac n2$，则$n - (i-j) < i - j$，可以对应于复制串上$i,j+n$之间传物品
所以直接在复制串上以区间长为$\frac n2$来处理。

对于$i$的答案为$\max(a_i+a_j+i-j)$，将定值$i$的部分提取出$\max$，那么我们只用维护$a_i-i$的最大值。因为是区间移动，所以单调队列维护。

知识点：
1、单调队列的写法

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<set>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;

namespace flyinthesky {

    const int MAXN = 1000000 + 5;

    int n, a[MAXN * 2];
    int l, r, que[MAXN * 4], ans = 0;

    void clean() {
    }
    int solve() {
        clean();
        scanf("%d", &n);
        for (int i = 1; i <= n; ++i) scanf("%d", &a[i]), a[i + n] = a[i];
        l = 1, r = 1;
        for (int i = 1; i <= 2 * n; ++i) {
            while (l <= r && que[l] < i - n / 2) ++l;
            ans = max(ans, i + a[i] + a[que[l]] - que[l]);
            while (l <= r && a[que[r]] - que[r] <= a[i] - i) --r;
            que[++r] = i;
        }
        cout << ans;
        return 0;
    }
}
int main() {
    flyinthesky::solve();
    return 0;
}