51Nod 1593 公园晨跑(RMQ,ST表)

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 }

 

转载于:https://www.cnblogs.com/ccsu-kid/p/10617555.html

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/101017.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • mybatis错误——java.io.IOException: Could not find resource com/xxx/xxxMapper.xml

    Mybatis加载Mapper的xml出现java.io.IOException: Could not find resource com/xxx/xxxMapper.xml

  • 芯片的架构_意法半导体

    芯片的架构_意法半导体在了解这些架构之前,我们应该先了解一下复杂指令集(CISC)和精简指令集(RISC)。怎么说这两个的区别呢?CISC的设计思路更加注重性能的发展,是一种高性能高功耗的芯片,在高密度的计算上更具有优势;RISC的设计思路更注重低功耗小尺寸,多用于移动端设备,在重复性任务上占优。举一个简单的例子来说明这个情况,我们在B站上常说的一键三连,CISC会把“点赞”“投币”“收藏”整理成一条指令在缓存中,再由处理器处理;但是对于RISC来说就是三条指令了先“点赞”再“投币”最后“收藏”,这样做的缺点就是很依赖内存带宽了

  • Java异常分类及处理

    Java异常分类及处理

  • docker_docker一键部署

    docker_docker一键部署1、安装mysql自行安装2、安装Gogs自行安装3、安装drone/dronedockerrun-d\–volume=/var/lib/drone:/data\–env=DRONE_DEBUG=true\–env=DRONE_LOGS_TRACE=true\–env=DRONE_LOGS_DEBUG=true\–env=DRONE_LOGS_PRETTY=true\–env=DRONE_AGENTS_ENABLED=true\–env=

  • 静态路由的基本配置实验总结_三个路由器配置静态路由

    静态路由的基本配置实验总结_三个路由器配置静态路由静态路由的基本配置静态路由配置图如下PC1IP地址:192.168.1.2PC2IP地址:192.168.2.2PC3IP地址:192.168.3.2PC4IP地址:192.168.4.2R1IP地址:f1/0192.168.3.1f0/2192.168.4.1s2/01.1.1.1R2IP地址:f0/0192.168.1.1f1/0192.168.2.1s2/01.1.1.2配置好四台电脑

  • 杭电OJ2058_杭电OJ

    杭电OJ2058_杭电OJ杭电OJ2058我写的超时了下面是不超时的#include<stdio.h>#include<math.h>intmain(){ intn,m,i,j; while(scanf(“%d%d”,&n,&m)!=EOF){ if(n==0&&m==0) break; for(j=(int)sqrt((double)(2*m));j>=1;j–){ i=(

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号