社区讨论

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 条回复,欢迎继续交流。

正在加载回复...