_zjr @ 2018-01-07 23:24:12
下面是我写的RMQ(本蒟蒻只会用RMQ)
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
const int mxn=1000001;
using namespace std;
int q[mxn][20],p[mxn][20];
int n,k;
int max(int a,int b){
if(a>b) return a;
else return b;
}
int min(int a,int b){
if(a<b) return a;
else return b;
}
int find(int l,int r){
int i;
for(int i=1;i<=16;i++){
if(pow(2,i)>r){
i-=1;
}
}
return max(q[l][i],q[l+r-(int)pow(2,i)][i]);
}
int find2(int l,int r){
int i;
for(int i=1;i<=16;i++){
if(pow(2,i)>r){
i-=1;
}
}
return min(p[l][i],p[l+r-(int)pow(2,i)][i]);
}
int main(){
cin>>n>>k;
for(int i=1;i<=n;i++){
cin>>q[i][0];
p[i][0]=q[i][0];
}
for(int i=1;i<=16;i++){
for(int j=1;j<=n;j++){
q[j][i]=max(q[j][i-1],q[j+(int)pow(2,i-1)][i-1]);
p[j][i]=min(p[j][i-1],p[j+(int)pow(2,i-1)][i-1]);
}
}
for(int j=1;j<=n;j++) cout<<find2(j,k)<<' ';
cout<<endl;
for(int j=1;j<=n;j++) cout<<find(j,k)<<' ';
return 0;
}
然后,,,所有点超时
by iodwad @ 2018-01-07 23:38:10
你每次手动算log2肯定超时了呀。。。这个东西可以预处理出来的
by λᴉʍ @ 2018-01-08 07:42:06
你预处理出log应该就不会T了
by 微雨燕双飞 @ 2018-01-31 20:18:50
哇,第一次看人RMQ手动写log的(虽然我曾经也这样),改掉应该就没事了。