ST算法
发布日期:2022-03-30 18:18:25 浏览次数:28 分类:博客文章

本文共 1054 字,大约阅读时间需要 3 分钟。

ST算法/*********************************title:
  poj1185 problem:
士兵杀敌(三)algorithm:   STtime:
   2012-7-23write :
  HuHanwu*********************************/#include  #include  #include  #define max(a,b) (a>b?a:b)#define min(a,b) (a
int i,j,m;
for(i=1;i<=n;i++){mi[i][0]=mx[i][0]=w[i];}
m=floor(log((double)n)/log(2.0));
for(i=1;i<=m;i++)
for(j=n;j>=1;j--){
mx[j][i]=mx[j][i-1];
if(j+(1<<(i-1))<=n)mx[j][i]=max(mx[j][i],mx[j+(1<<(i-1))][i-1]);
mi[j][i]=mi[j][i-1];
if(j+(1<<(i-1)<=n))mi[j][i]=min(mi[j][i],mi[j+(1<<(i-1))][i-1]);
}}int rmqmin(int l,int r){
int m=floor(log((double)(r-l+1))/log(2.0));
return min(mi[l][m],mi[r-(1<
int m=floor(log((double)(r-l+1))/log(2.0));
return max(mx[l][m],mx[r-(1<
scanf("%d%d",&n,&q);
for(int i=1;i<=n;i++)scanf("%d",&w[i]);
rmqinit();
int l,r;
for(int i=1;i<=q;i++){
scanf("%d%d",&l,&r);
printf("%d\n",rmqmax(l,r)-rmqmin(l,r));
}
return 0;}

转载地址:https://www.cnblogs.com/codeloveme/archive/2012/08/03/2621902.html 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:SpringBoot2.X快速入门案例
下一篇:hdu 3033 分组背包(反分组背包)

发表评论

最新留言

做的很好,不错不错
[***.77.167.74]2022年12月04日 14时22分27秒