社区讨论
RMQ算法MLE还有救吗
P4392[BalticOI 2007] Sound 静音问题参与者 7已保存回复 11
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 11 条
- 当前快照
- 1 份
- 快照标识符
- @m1iuwrn8
- 此快照首次捕获于
- 2024/09/26 13:31 去年
- 此快照最后确认于
- 2025/11/05 00:09 4 个月前
CPP
#include <bits/stdc++.h>
#include <cmath>
//#define int long long
//using namespace std;
int n,m,k,c;
int a[1000000];
int f[1000005][20];
int f2[1000005][20];
int g[1000005];
signed main(){
// ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
std::cin>>n>>m>>c;
for(int i=1;i<=n;i++){
std::cin>>a[i];
}
g[0] = -1;
for(int i=1;i<=n;i++){
f2[i][0]=f[i][0]=a[i];
g[i] = g[i >> 1] + 1;
}
for (int i=1;i<=20;++i){
for (int j=1;j+(1<<i)-1<=n;++j){
f[j][i]=std::max(f[j][i-1],f[j+(1<<(i-1))][i-1]);
}
}
for (int i=1;i<=20;++i){
for (int j=1;j+(1<<i)-1<=n;++j){
f2[j][i]=std::min(f2[j][i-1],f2[j+(1<<(i-1))][i-1]);
}
}
bool flag=0;
for(int x=1;x<=n-m+1;x++){
int y=x+m-1;
k=g[y - x + 1];
if(std::max(f[x][k], f[(int)(y - pow(2,k) + 1)][k])-std::min(f2[x][k], f2[(int)(y - pow(2,k) + 1)][k])<=c){
std::cout<<x<<"\n";
flag=1;
}
}
if(!flag){
std::cout<<"NONE";
}
return 0;
}
回复
共 11 条回复,欢迎继续交流。
正在加载回复...