给出一个长度为n序列\(a_i\)，定义第i个位置和第j个位置的距离为\(s[i][j]=\min(|i-j|,n-|i-j|)\)，定义两个位置的权值为\(a_i+a_j+s[i][j]\)，询问最大的权值，\(n\leq 10^6\)。

解

注意到所谓的距离，即环上的距离公式，所以问题与环有关，于是拆环成链，再补一截一模一样的序列在原序列后，不妨按照区间问题的解决办法，枚举一个右端点i，再枚举左端点j，自然\(i>j\),设\(i-j\leq n/2\)

\(i-j\leq n/2:\)

此时，显然可以在新序列上表现旧序列i，j的距离

\(i-j> n/2\)

此时存在另外一个\(j'=j+n\)，满足i,j'间距离\(j'-i=j+n-i=n-|i-j|\)

于是只要在环上满足\(i-j\leq n/2\)，就可以表现原序列也即环的所有的距离，其实也可以这样感性理解，因为所谓的再补一截，也就是一条穿越原来的环2次的路径，对于其中一小段路径的长度记做s1,对于这一小段路径的两个端点，在环上互达有两条路径，较小的那条为距离，于是当\(s1\leq n/2\)，必然为所谓的距离。

于是我们只要枚举右端点，在枚举合法的左端点，寻找它们的最大值，这个我们时是可以利用单调递减的单调队列维护的。

参考代码：

#include 
    
     #include 
     
      #include 
      
       #define il inline#define ri register#define pi pair
       
        using namespace std;deque
        
         Q;int a[2000001];il int max(int,int);int main(){    int n,n2,ans(0);scanf("%d",&n),n2=n<<1;    for(int i(1);i<=n;++i)scanf("%d",&a[i]),a[i+n]=a[i];    for(int i(1),j;i<=n2;++i){        while(Q.size()&&Q.front().first
         
          >1))Q.pop_front(); if(Q.size())ans=max(ans,Q.front().second+a[i]+i); while(Q.size()&&Q.back().second
          
           b?a:b;}