51 Nod 1593公園晨走(RMQ、ST表)

13458 ワード

http://www.51nod.com/Challenge/Problem.html#!ヽoo!ツproblemId=1593
考え方
ST表については、このブログを見ることをオススメします。https://www.cnblogs.com/YSFAC/p/7189571.html
胡小兔大王の問題解を参考にして解決しました。よく書いています。見てください。ここはくどいです。
 1 #define IO std::ios::sync_with_stdio(0);
 2 #include 
 3 #define iter ::iterator
 4 using namespace  std;
 5 typedef long long ll;
 6 typedef pairP;
 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]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<1)==j?++i:i;
32         //printf("j=%d: %d
",j,lg[j]);
33 } 34 for(int j=1;(1<2*n;j++){ 35 for(int i=1;i+(1<1<=2*n;i++){ 36 ma[i][j]=check(ma[i][j-1],ma[i+(1<1))][j-1],1); 37 mi[i][j]=check(mi[i][j-1],mi[i+(1<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<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<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
",query(y+1,x-1)); 77 else printf("%lld
",query(y+1,n+x-1)); 78 } 79 return 0; 80 }