环路运输

题意：
有一个n个节点的环，每一个节点有一个权值Ai,求两个节点i,j之间的Ai+Aj+dis(i,j)(i到j的距离)最大为多少？

思路：
单调队列
首先将环转换成链，即加一段（n+1）~ (2*n),a[n+i]=a[i] (n>=i>=0)。
在环上两点的距离小于等于n/2。
设Ai+Aj+dis(i,j)=Ai+Aj+(i-j) (i>j)=(Ai+i)+(Aj-j) (i>j且i-j<=n/2)
因为Ai+i是确定的，所以只需要求i的前（n/2）个节点的（Aj-j）的最大值，可以用单调递减队列维护,结果为i+Ai+（Aj-j）的最大值。

代码：

#include<bits/stdc++.h>

#define ll long long
#define eps 1e-8

using namespace std;

const ll inf=1e9+7;

int a[2000005];

struct q
{
    int x, val;
}q[2000005];

int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        a[n+i]=a[i];
    }
    int l=0, r=0, ma=0;
    for(int i=1;i<=2*n;i++)
    {
        while(l<r&&i-q[l].x>n/2)
        {
            l++;
        }
        if(l==r)
        {
            q[r].val=a[i]-i;
            q[r].x=i;
            r++;
        }
        else
        {
            while(l<r&&q[r-1].val<=a[i]-i)
            {
                r--;
            }
            if(l<r)
            {
                ma=max(a[i]+i+q[l].val,ma);
            }
            q[r].val=a[i]-i;
            q[r].x=i;
            r++;
        }
    }
    cout << ma << endl;
    return 0;
}