1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112
| #include<bits/stdc++.h> using namespace std; #define rep(i,a,n) for(int i=(a);i<(n);i++) #define per(i,a,n) for(int i=(n-1);i>=(a);i--) #define fi first #define se second #define lson l,mid,rt<<1 #define rson mid+1,r,rt<<1|1 typedef pair <int,int> pII; typedef long long ll; const ll INF = 1e11;
const int maxn = 2e5 + 10; ll h[maxn],d[maxn],A[maxn],B[maxn]; int mmax[maxn<<2],mmin[maxn<<2]; template <class T> bool read(T &x){ char c; bool op = 0; while(c = getchar(), c < '0' || c > '9') if(c == '-') op = 1; else if(c == EOF) return 0; x = c - '0'; while(c = getchar(), c >= '0' && c <= '9') x = x * 10 + c - '0'; if(op) x = -x; return 1; } inline int Max(int a,int b){ return A[a] > A[b] ? a : b; } inline int Min(int a,int b){ return B[a] < B[b] ? a : b; } inline ll Mmax(ll a,ll b){ return a>b?a:b; } int m,n; void pushup(int rt){ mmax[rt] = Max(mmax[rt<<1],mmax[rt<<1|1]); mmin[rt] = Min(mmin[rt<<1],mmin[rt<<1|1]); } void build(int l,int r,int rt){ if(l==r){ mmax[rt] = l; mmin[rt] = l; return ; } int mid = (r+l)>>1; build(lson);build(rson); pushup(rt); } int query_max(int L,int R,int l,int r,int rt){ if(L <= l && r <= R) return mmax[rt]; int mid = (l+r) >> 1; ll res = 0; if(L <= mid) res = Max(res,query_max(L,R,lson)); if(mid < R) res = Max(res,query_max(L,R,rson)); return res; } int query_min(int L,int R,int l,int r,int rt){ if(L <= l && r <= R) return mmin[rt]; int mid = (l+r) >> 1; ll res = 0; if(L <= mid) res = Min(res,query_min(L,R,lson)); if(mid < R) res = Min(res,query_min(L,R,rson)); return res; } int main(){ #ifdef LOCAL freopen("1.in","r",stdin); #endif scanf("%d%d",&n,&m); rep(i,2,n+2) read(d[i]),d[n+i] = d[i]; rep(i,2,n*2+1) d[i] += d[i-1]; rep(i,1,n+1){ ll hh;read(hh); h[i] = h[i+n] = hh; } A[0] = -INF;B[0] = INF; rep(i,1,n+n+1){ A[i] = 2*h[i] + d[i]; B[i] = d[i] - 2*h[i]; } build(1,n*2,1); while(m--){ int l,r;read(l);read(r); if(l<=r){ int st = query_max(r+1,l+n-1,1,2*n,1); int ed = query_min(r+1,l+n-1,1,2*n,1); ll ans; if(st == ed){ int st1 = Max(query_max(st+1,l+n-1,1,2*n,1),query_max(r+1,st-1,1,2*n,1)); int ed1 = Min(query_min(ed+1,l+n-1,1,2*n,1),query_min(r+1,ed-1,1,2*n,1)); ans = Mmax(A[st] - B[ed1],A[st1] - B[ed]); }else ans = A[st] - B[ed]; printf("%lld\n",ans); }else{ int st = query_max(r+1,l-1,1,2*n,1); int ed = query_min(r+1,l-1,1,2*n,1); ll ans; if(st == ed){ int st1 = Max(query_max(st+1,l-1,1,2*n,1),query_max(r+1,st-1,1,2*n,1)); int ed1 = Min(query_min(ed+1,l-1,1,2*n,1),query_min(r+1,ed-1,1,2*n,1)); ans = Mmax(A[st] - B[ed1],A[st1] - B[ed]); }else ans = A[st] - B[ed]; printf("%lld\n",ans); } } return 0; }
|