https://www.51nod.com/Challenge/Problem.html#!#problemId=1593
题意：
环形公园里有n棵树，一些孩子会占据几棵连续的树，m组询问，每组询问中一只猴子要选两棵树，从一棵到另一棵，中间不经过孩子，消耗的能量为两树间距离+2*两棵树的高，求消耗能量最大值。
思路：
https://blog.csdn.net/ZLH_HHHH/article/details/74887389
这篇讲的非常清楚。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 600000+100;
typedef long long ll;

int n,m,d[maxn],h[maxn],minn[20][maxn],maxx[20][maxn];
ll ds[maxn],A[maxn],B[maxn];

void RMQ_init()
{
    for(int i=1;i<=2*n;i++)maxx[0][i]=i,minn[0][i]=i;
    for(int k=1;(1<<k)<=2*n;k++)
    {
        for(int i=1;i+(1<<k)-1<=2*n;i++)
        {
            maxx[k][i]= (A[maxx[k-1][i]] > A[maxx[k-1][i+(1<<(k-1))]] ?maxx[k-1][i]:maxx[k-1][i+(1<<(k-1))]);
            minn[k][i]= (B[minn[k-1][i]] < B[minn[k-1][i+(1<<(k-1))]] ?minn[k-1][i]:minn[k-1][i+(1<<(k-1))]);
        }
    }
}

int RMQ(int l,int r,int flag)
{
    int k=0;
    while((1<<(k+1))<=(r-l+1))k++;
    if(flag==0)return A[maxx[k][l]] > A[maxx[k][r-(1<<k)+1]] ?maxx[k][l]:maxx[k][r-(1<<k)+1];
    else return B[minn[k][l]] < B[minn[k][r-(1<<k)+1]] ?minn[k][l]:minn[k][r-(1<<k)+1];
}

void solve(int a,int b)
{
    int x=RMQ(a,b,0),y=RMQ(a,b,1);
    if(x!=y)printf("%lld\n",A[x]-B[y]);
    else
    {  
        ll ans=-(1<<30);
        if(y!=a)ans=max(ans,A[x]-B[RMQ(a,y-1,1)]);
        if(y!=b)ans=max(ans,A[x]-B[RMQ(y+1,b,1)]);
        if(x!=a)ans=max(ans,A[RMQ(a,x-1,0)]-B[y]);
        if(x!=b)ans=max(ans,A[RMQ(x+1,b,0)]-B[y]);
        printf("%lld\n",ans);
    }   
}

int main()
{
    //freopen("input.in","r",stdin);
    int a,b;
    cin>>n>>m;
    for(int i=1;i<=n;i++)scanf("%d",&d[i]);
    for(int i=1;i<=n;i++)scanf("%d",&h[i]);
    for(int i=n+1;i<=2*n;i++)d[i]=d[i-n],h[i]=h[i-n];
    for(int i=1;i<=2*n;i++)ds[i]=ds[i-1]+d[i-1];
    for(int i=1;i<=2*n;i++)A[i]=ds[i]+2*h[i];
    for(int i=1;i<=2*n;i++)B[i]=ds[i]-2*h[i];
    RMQ_init();
    while(m--)
    {
        scanf("%d%d",&a,&b);
        a--,b++;
        swap(a,b);
        if(a>b)b+=n;
        solve(a,b);
    }
    return 0;
}