RMQ算法MLE还有救吗
查看原帖
RMQ算法MLE还有救吗
973278
Benny10楼主2024/9/26 13:31
#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;
}
2024/9/26 13:31
加载中...