题目描述
第一行有三个整数\(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();
}
}
标签:Sound,10,typedef,leq,队列,max,long,int,单调
From: https://www.cnblogs.com/ruoye123456/p/18374895