51nod1593 公园晨跑

51nod1593 公园晨跑

Description

有一只猴子，他生活在一个环形的公园里。有n棵树围绕着公园。第i棵树和第i+1棵树之间的距离是 di ，而第n棵树和第一棵树之间的距离是 dn 。第i棵树的高度是 hi 。
这只猴子每天要进行晨跑。晨跑的步骤如下：
· 他先选择两棵树；
· 然后爬上第一棵树；
· 再从第一棵树上下来，接着围绕着公园跑（有两个可能的方向）到第二棵树，然后爬上第二棵树；
· 最后从第二棵树上下来。
但是有一些小孩会在连续的一些树上玩耍。所以猴子不能经过这些树。
比如现在猴子选择的第x棵和第y棵树，那么该早晨他消耗的能量是 2(hx+hy)+dist(x,y) 。由于某一条路径是被小孩子占据的，所以他只能跑另外一条，因此 dist(x,y) 是确定的。
现在给出第i天，孩子们会在第 ai 棵树和 bi 棵树之间玩耍。具体的，如果 ai≤bi ，那么孩子玩耍的区间就是 [ai,bi] ，否则孩子玩耍的区间就是 [ai,n]⋃[1,bi] 。
请帮助这只猴子找出两棵树，让他晨跑的时候他能够消耗最大的能量。

Input

单组测试数据。
第一行有两个整数 n 和m (3≤n≤10^5, 1≤m≤10^5)，表示树的数目，以及猴子跑步的天数。
第二行有n个整数d1,d2,…,dn (1≤di≤10^9)，表示树之间的距离。
第三行有n个整数h1,h2,…,hn (1≤hi≤10^9)，表示树的高度。
接下来m行，第一行有两个整数 ai和bi (1≤ai,bi≤n)，描述每一天孩子玩耍的区间。输入保证至少有两个棵树孩子不会进行玩耍，这样猴子每天都可以晨跑了。

Output

对于每一天，输出猴子消耗的最大能量。

Input示例

样例输入1
5 3
2 2 2 2 2
3 5 2 1 4
1 3
2 2
4 5

Output示例

样例输出1
12
16
18

Solution

环的情况比较难以处理 所以我们考虑拆环为一个2n的链
然后我们把距离算出来，di表示第i号点到第一号点的距离
我们要求|dx-dy|+2(hx+hy)
令x

Code

#include <cstdio>
#include <cstring>
#include <algorithm>
#define fo(i,a,b) for(i=a;i<=b;i++)
#define L rt<<1
#define R rt<<1|1
using namespace std;
const int N=100005;
const long long inf =-1234567891011;
typedef long long ll;
ll h,ans1,ans2,s1[N<<1],s2[N<<1],a[N<<1];
int n,m,i,s,l,r,u,ma1,ma,mi1,mi,t;
struct edge{ll x; int y; edge( ){x=inf;}
};
inline ll max(ll a,ll b) { return a>b?a:b;}
struct pp{edge tr[N<<3];inline void pushup(int rt){if (tr[L].x>tr[R].x){tr[rt].x=tr[L].x;tr[rt].y=tr[L].y;}else {tr[rt].x=tr[R].x;tr[rt].y=tr[R].y;}}inline void insert(int rt,int x,int l,int r,ll y){if (l==r) {tr[rt].x=y;tr[rt].y=x;return;}int mid=(l+r)>>1;if (x<=mid) insert(L,x,l,mid,y);else insert(R,x,mid+1,r,y);pushup(rt);}inline edge merge(edge a,edge b){edge p;if (a.x>b.x) p.y=a.y; else p.y=b.y;p.x=max(a.x,b.x);return p; }edge query(int rt,int l,int r,int x,int y){if (x<=l&&y>=r) return tr[rt];int mid=(l+r)>>1;edge p,w;if (x<=mid) p=query(L,l,mid,x,y);if (y>mid) w=query(R,mid+1,r,x,y); p=merge(p,w);return p;}
} T1,T2;
ll read(){ll sum=0;char c=getchar();while (c<'0'||c>'9') c=getchar();while (c>='0'&&c<='9'){sum=sum*10+c-'0';c=getchar();}return sum;
}
int re(){int sum=0;char c=getchar();while (c<'0'||c>'9') c=getchar();while (c>='0'&&c<='9'){sum=sum*10+c-'0';c=getchar();}return sum;
}
void write(ll x)
{if (x>9) write(x/10);putchar(x%10+'0');
}int main(){//freopen("1.in","r",stdin);//freopen("1.out","w",stdout);scanf("%d%d",&n,&m);s=n<<1;fo(i,1,n) scanf("%lld",&a[i]);for(i=n+1,t=1;i<=s;i++,t++) a[i]=a[t];fo(i,1,s) s1[i]=s1[i-1]+a[i-1],s2[i]=s1[i]; fo(i,1,n){scanf("%lld",&h);h<<=1;s1[i]+=h,s2[i]-=h;s1[i+n]+=h,s2[i+n]-=h;}fo(i,1,s){T1.insert(1,i,1,s,s1[i]);T2.insert(1,i,1,s,-s2[i]);}while (m){m--;l=re(),r=re();if (l<=r){u=r+1;r=n+l-1;l=u;} else {r++,l--;swap(l,r);}ma=T1.query(1,1,s,l,r).y;mi=T2.query(1,1,s,l,r).y;if (ma==mi){ma1=-1;if (ma>l) ma1=T1.query(1,1,s,l,ma-1).y;if (ma<r){u=T1.query(1,1,s,ma+1,r).y;if (ma1==-1||s1[ma1]<s1[u]) ma1=u;}mi1=-1;if (mi>l) mi1=T2.query(1,1,s,l,mi-1).y;if (mi<r) {u=T2.query(1,1,s,mi+1,r).y;if (mi1==-1||(-s2[mi1])<(-s2[u])) mi1=u;}ans1=s1[ma1]-s2[mi],ans2=s1[ma]-s2[mi1];write(max(ans1,ans2));printf("n");} else {write(s1[ma]-s2[mi]);printf("n");}}
}