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

全栈程序员-站长 • 2021年7月3日下午7:00 • 未分类 • 阅读 105

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 }