首页 > 代码库 > hiho1068(RMQ)
hiho1068(RMQ)
题目连接:https://hihocoder.com/problemset/problem/1068?sid=1069788
RMQ
1 #include<cstdio> 2 #include<cstring> 3 #include<cmath> 4 #include<algorithm> 5 using namespace std; 6 const int maxn=1e6+10; 7 const int inf=0x3f3f3f3f; 8 9 int dp[maxn][21]; 10 11 int main() 12 { 13 int n; 14 scanf("%d",&n); 15 for(int i=1;i<=n;i++) 16 scanf("%d",&dp[i][0]); 17 for(int i=0;i<21;i++) 18 dp[0][i]=inf; 19 20 int len=log2(n); 21 for(int j=1;j<=len;j++) 22 for(int i=1;(i+(1<<j)-1)<=n;i++) 23 dp[i][j]=min(dp[i][j-1],dp[i+(1<<j-1)][j-1]); 24 int m,s,e,ans; 25 scanf("%d",&m); 26 while(m--) 27 { 28 scanf("%d%d",&s,&e); 29 int k=log2(e-s+1); 30 ans=min(dp[s][k],dp[e-(1<<k)+1][k]); 31 printf("%d\n",ans); 32 } 33 return 0; 34 35 }
hiho1068(RMQ)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。