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
胡小兔大王の問題解を参考にして解決しました。よく書いています。見てください。ここはくどいです。
考え方
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 }