萌新求助
查看原帖
萌新求助
368791
FL_sleake楼主2024/1/23 16:52

大部分题解区间最小值是用ST表维护的,我用的set进行维护,思路是一样的,查不出错哪了。求大佬帮忙看看/bx

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,k,a[200010],id=0;
set<int> s;
signed main(){
	cin>>n>>k;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=n;i++){
		int r=i;
		while(a[r+1]>a[r]&&r+1<=n&&r+1-i+1<=k) r++;
		if(r-i+1>=k){
			for(int x=1;x<=n;x++) cout<<a[x]<<" ";
			return 0;
		}
		i=r;
	}
	id=n-k+1;
	for(int i=n;i>=n-k+1;i--) s.insert(a[i]);
	for(int i=n-k;i>=1;i--){
		s.erase(s.find(a[i+k]));
		if(a[i]<*s.begin()) id=i,s.insert(a[i]);
		else break;
	}
	sort(a+id,a+id+k);
	for(int i=1;i<=n;i++) cout<<a[i]<<" ";
	return 0;
}
2024/1/23 16:52
加载中...