51Nod 1593 公园晨跑（RMQ，ST表）

http://www.51nod.com/Challenge/Problem.html#!#problemId=1593

思路

关于ST表，建议看这篇博客：https://www.cnblogs.com/YSFAC/p/7189571.html

参考胡小兔大佬的题解搞定了，写的很好，不妨看下，这里就不罗嗦了

 1 #define IO std::ios::sync_with_stdio(0);  2 #include <bits/stdc++.h>  3 #define iter ::iterator  4 using namespace std;  5 typedef long long ll;  6 typedef pair<ll,ll>P;  7 #define pb push_back  8 #define se second  9 #define fi first 10 #define rs o*2+1 11 #define ls o*2 12 const ll inf=0x7fffffffffffffff; 13 const int N=2e5+5; 14 ll d[N],h[N],a[N],b[N]; 15 ll n,q; 16 ll ma[N][20],mi[N][20],lg[N]; 17 int check(int x,int y,int z){ 18 if(z==1)return a[x]>a[y]?x:y; 19 return b[x]<b[y]?x:y; 20 } 21 void init(){ 22 a[0]=-inf,b[0]=inf; 23 ll s=0; 24 for(ll i=1;i<=2*n;i++){ 25 s+=d[i]; 26 a[i]=s+h[i]; 27 b[i]=s-h[i]; 28 ma[i][0]=mi[i][0]=i; 29  } 30 for(ll j=1,i=0;j<=2*n;j++){ 31 lg[j]=1<<(i+1)==j?++i:i; 32 //printf("j=%d: %d\n",j,lg[j]); 33  } 34 for(int j=1;(1<<j)<=2*n;j++){ 35 for(int i=1;i+(1<<j)-1<=2*n;i++){ 36 ma[i][j]=check(ma[i][j-1],ma[i+(1<<(j-1))][j-1],1); 37 mi[i][j]=check(mi[i][j-1],mi[i+(1<<(j-1))][j-1],0); 38  } 39  } 40 } 41 ll getma(int l,int r){ 42 if(l>r)return 0; 43 int j=lg[r-l+1]; 44 return check(ma[l][j],ma[r-(1<<j)+1][j],1); 45 } 46 ll getmi(int l,int r){ 47 if(l>r)return 0; 48 int j=lg[r-l+1]; 49 return check(mi[l][j],ma[r-(1<<j)+1][j],0); 50 } 51 ll query(int l,int r){ 52 int x=getma(l,r); 53 int y=getmi(l,r); 54 if(x!=y)return a[x]-b[y]; 55 int x1=check(getma(l,x-1),getma(x+1,r),1); 56 int y1=check(getmi(l,x-1),getmi(x+1,r),0); 57 return max(a[x1]-b[y],a[x]-b[y1]); 58 } 59 int main(){ 60 scanf("%d%d",&n,&q); 61 for(int i=1;i<=n;i++){ 62 int x=i%n+1; 63 int y=i%n+1+n; 64 scanf("%lld",&d[x]); 65 d[y]=d[x]; 66  } 67 for(int i=1;i<=n;i++){ 68 scanf("%lld",&h[i]); 69 h[i]*=2; 70 h[i+n]=h[i]; 71  } 72  init(); 73 while(q--){ 74 int x,y; 75 scanf("%d%d",&x,&y); 76 if(x>y)printf("%lld\n",query(y+1,x-1)); 77 else printf("%lld\n",query(y+1,n+x-1)); 78  } 79 return 0; 80 }