Sound（单调队列）

ruoye123456 / 2024-08-23 / 原文

题目描述
第一行有三个整数$n,m,c(1\leq n\leq 10^6,1\leq m\leq 10^4,0\leq c\leq 10^4)$。

第二行$n$个非负整数$a_1,a_2,\dots,a_n(1\leq a_i\leq 10^6)$。
求有多少个i满足[i...i+m-1]区间的极差<=c
输出
从小到大输出所有满足条件的$i$，一行一个。如果没有$i$满足条件，则输出NONE。
样例输入 Copy
7 2 0
0 1 1 2 3 2 2
样例输出 Copy
2
6

简单的单调队列，所有的$l_{i+1}>=l_{i}$,且$r_{i+1}>=r{i}$的问题都可以考虑单调队列，某些区间问题若离线后也可单调队列

#include<bits/stdc++.h>
using namespace std;
#define x first
#define y second
typedef pair<int,int> PII;
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef vector<string> VS;
typedef vector<int> VI;
typedef vector<vector<int>> VVI;
inline int log_2(int x) {return 31-__builtin_clz(x);}
inline int popcount(int x) {return __builtin_popcount(x);}
inline int lowbit(int x) {return x&-x;}
const int N = 1e6+10;
int a[N],q_max[N],q_min[N],Max[N],Min[N];
void solve()
{
	int n,m,c;
	cin>>n>>m>>c;
	int h_max = 1,t_max = 0;
	int h_min = 1,t_min = 0;
	for(int i=1;i<=n;++i) 
	{
		cin>>a[i];
		//对于j<k若k的条件完胜j则弹出j
		while(h_max<=t_max&&a[i]>=a[q_max[t_max]]) t_max--;
		while(h_min<=t_min&&a[i]<=a[q_min[t_min]]) t_min--;
		q_max[++t_max] = i;
		q_min[++t_min] = i;
		if(i>=m)
		{
			while(h_max<=t_max&&q_max[h_max]<i-m+1) h_max++;
			if(h_max<=t_max) Max[i] = a[q_max[h_max]];
			while(h_min<=t_min&&q_min[h_min]<i-m+1) h_min++;
			//cout<<h_min<<'\n';
			if(h_min<=t_min) Min[i] = a[q_min[h_min]];
		}
	}
	bool ok = false;
	for(int i=m;i<=n;++i) 
	{
		//cout<<i-m+1<<' '<<Max[i]<<' '<<Min[i]<<'\n';
		if(Max[i]-Min[i]<=c) ok = true,cout<<i-m+1<<"\n";
	}
	if(!ok) cout<<"NONE\n";
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int T = 1;
	//cin>>T;
	while(T--)
	{
		solve();
	}
}