2021-2022ACM集训队月度编程挑战赛第二轮：最大值与最小值的选择

题意&＃xff1a;
$给你一个n个数的数组和一个k$
$1<\&＃61;n,k<\&＃61;1e5,$
$a1,a2,......an$
$1<\&＃61;ai<\&＃61;n$
$求一个最长区间[l,r]$
$满足这个区间的最大值-最小值<\&＃61;k$
思路&＃xff1a;
$假设当前区间为mid$
$如果存在长度为mid的区间满足最大值-最小值<\&＃61;k$
$说明mid可以变大$
$否则mid变小$

$因此考虑二分查找mid$
$时间复杂度logn$

$查询区间最大值和最小值可以考虑$
$树状数组/st表/线段树$

$线段树查询nlogn总时间复杂度nlognlogn$
$st表查询o1总时间复杂度nlogn$
$树状数组与线段树类似$

$其实还有个很妙的做法$
$set\&＃43;双指针动态维护nlogn$
$每次假设i这个下标为区间右端点$
$找到最大的一个左端点$
$同时更新答案$
$方法一$
时间复杂度&＃xff1a;$线段树\&＃43;二分Onloglogn$

#include
#include
#include
#include using namespace std;const int N &＃61; 200010;int n , m , k ;
struct Node
{int l, r;int v , minv ; // 区间[l, r]中的最大值和最小值
}tr[N * 4];
int a[N];void pushup(int u) // 由子节点的信息&＃xff0c;来计算父节点的信息
{tr[u].v &＃61; max(tr[u<<1].v,tr[u<<1|1].v);tr[u].minv &＃61; min(tr[u<<1].minv,tr[u<<1|1].minv);
}void build(int u, int l, int r)
{if(l &＃61;&＃61; r) tr[u] &＃61; {l,r,a[r],a[r]};else{tr[u] &＃61; {l, r};int mid &＃61; r &＃43; l >> 1 ;build(u << 1 , l , mid ) , build(u << 1 | 1 , mid &＃43; 1 , r);pushup(u);}
}int query(int u, int l, int r)
{if(tr[u].l >&＃61; l && tr[u].r <&＃61; r) return tr[u].v ;int v &＃61; -1e9 ;int mid &＃61; tr[u].l &＃43; tr[u].r >> 1 ;if(l <&＃61; mid) v &＃61; max(v,query(u << 1 , l ,r));if(r > mid) v &＃61; max(v,query(u << 1 | 1 , l , r));return v ;
}int query1(int u, int l, int r)
{if(tr[u].l >&＃61; l && tr[u].r <&＃61; r) return tr[u].minv ;int v &＃61; 1e9 ;int mid &＃61; tr[u].l &＃43; tr[u].r >> 1 ;if(l <&＃61; mid) v &＃61; min(v,query1(u << 1 , l ,r));if(r > mid) v &＃61; min(v,query1(u << 1 | 1 , l , r));return v ;
}bool check(int mid)
{int x &＃61; mid ;for(int i &＃61; 1 ; i &＃43; x - 1 <&＃61; n ; i &＃43;&＃43;){if(query(1,i,i&＃43;x-1) - query1(1,i,i&＃43;x-1) <&＃61; k) return true ;}return false ;
}int main()
{cin >> n >> k ;for(int i &＃61; 1 ; i <&＃61; n ; i &＃43;&＃43;) scanf("%d",&a[i]);build(1,1,n);int l &＃61; 1 , r &＃61; n ;while(l < r){int mid &＃61; r &＃43; l &＃43; 1 >> 1 ;if(check(mid)) l &＃61; mid ;else r &＃61; mid - 1 ;}cout << l << "\n" ;return 0;
}


$方法二$
时间复杂度&＃xff1a;$set\&＃43;双指针Onlogn$

#include
#define sz(x) ((int)(x).size())
using namespace std;
const int N &＃61; 1e6 &＃43; 10 ;int n , k ;
int a[N] ;signed main()
{cin >> n >> k ;for(int i &＃61; 1 ; i <&＃61; n ; i &＃43;&＃43;) scanf("%d",a &＃43; i) ;int res &＃61; 0 ;multiset<int> q ;for(int i &＃61; 1 , j &＃61; 1 ; i <&＃61; n ; i &＃43;&＃43;){q.insert(a[i]) ;while(q.size() && *--q.end() - *q.begin() > k && j <&＃61; n) {q.erase(q.find(a[j &＃43;&＃43;])) ;}res &＃61; max(res,sz(q)) ;}cout << res << "\n" ;return 0;
}


$方法三$
时间复杂度&＃xff1a;$st表\&＃43;二分Onlogn$

#include
using namespace std;
int a[100005],maxn[100005][30],minn[100005][30];
int n,k;
void st_prework(){for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;)maxn[i][0]&＃61;minn[i][0]&＃61;a[i];int t&＃61;log(n)/log(2)&＃43;1;for(int j&＃61;1;j<t;j&＃43;&＃43;)for(int i&＃61;1;i<&＃61;n-(1<<j)&＃43;1;i&＃43;&＃43;){minn[i][j]&＃61;min(minn[i][j-1],minn[i&＃43;(1<<(j-1))][j-1]);maxn[i][j]&＃61;max(maxn[i][j-1],maxn[i&＃43;(1<<(j-1))][j-1]);}
}
int getmax(int l,int r){int k&＃61;log(r-l&＃43;1)/log(2);return max(maxn[l][k],maxn[r-(1<<k)&＃43;1][k]);
}
int getmin(int l,int r){int k&＃61;log(r-l&＃43;1)/log(2);return min(minn[l][k],minn[r-(1<<k)&＃43;1][k]);
}
int main()
{cin>>n>>k;for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;)scanf("%d",&a[i]);st_prework();int anss&＃61;0;for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;){int l&＃61;i,r&＃61;n;while(l<r){int mid&＃61;(l&＃43;r&＃43;1)/2;int ans&＃61;getmax(i,mid)-getmin(i,mid);if(ans<&＃61;k){l&＃61;mid;}else {r&＃61;mid-1;}}anss&＃61;max(anss,l-i&＃43;1);}cout<<anss<<endl;
}