E11【模板】单调队列 滑动窗口最值

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int a[N], f[N], q[N]; // f[i]表示 a[i-k+1]~a[i]的最值

int main()
{
    int n, m; scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);

    int l = 1, r = 0; // 一开始队列空

    for (int i = 1; i <= n; i++) // 维护的是递增队列
    {
        while (l <= r && a[q[r]] >= a[i]) r--; // “踢”队尾的数，直到遇到“不能踢的数”

        q[++r] = i; // 然后自己住在队尾，那怕自己再小都有存在的必要，万一后面的数更大呢

        while (l <= r && i - q[l] >= m) l++; // “踢”队头的数，直到遇到“不该踢的数”

        if (i >= m) f[i] = a[q[l]]; // 这个时候队头是 a[i-m+1]~a[i]的最小值
    }
    for (int i = m; i <= n; i++) printf("%d ", f[i]); printf("\n");

    l = 1, r = 0; // 一开始队列空

    for (int i = 1; i <= n; i++) // 维护的是递减队列
    {
        while (l <= r && a[q[r]] <= a[i]) r--; // “踢”队尾的数，直到遇到“不能踢的数”

        q[++r] = i; // 然后自己住在队尾，那怕自己再小都有存在的必要，万一后面的数更小呢

        while (l <= r && i - q[l] >= m) l++; // “踢”队头的数，直到遇到“不该踢的数”

        if (i >= m) f[i] = a[q[l]]; // 这个时候队头是 a[i-m+1]~a[i]的最大值
    }
    for (int i = m; i <= n; i++) printf("%d ", f[i]); printf("\n");

    return 0;
}

$O(nlogk)$ 做法，思路较简单，代码较短（我不会告诉你这份代码之所以能过是因为数据太水了）

#include<bits/stdc++.h>

using namespace std;

const int N = 1e6 + 10 ;

int a [ N ] , minn [ N ] , maxx [ N ] ;

multiset < int > window ;

multiset < int > :: iterator pos [ N ] ;

int main ( )

{
	
	ios :: sync_with_stdio ( false ) ;
	
	cin . tie ( 0 ) ;
	
	cout . tie ( 0 ) ;
	
	register int n , k ;
	
	cin >> n >> k ;
	
	for ( register int i = 1 ; i <= n ; i++ )
	
	{
		
		cin >> a [ i ] ;
		
	}
	
	for ( register int i = 1 ; i <= n ; i ++ )
	
	{
		
		window . insert ( a [ i ] ) ;
		
		if ( i >= k )
		
		{
			
			multiset < int > :: iterator it2 = window . begin ( ) ;
			
			minn [ i ] = * it2 ;
			
			multiset < int > :: iterator it3 = window . end ( ) ;
			
			it3 -- ;
			
			maxx [ i ] = * it3 ;
			
			multiset < int > :: iterator it4 = window . find ( a [ i - k + 1 ] ) ;
			
			window . erase ( it4 ) ;
			
		}
		
	}
	
	for ( register int  i = k ; i <= n ; i ++ )
	
	{
		cout << minn [ i ] << ' ' ;
		
		if ( i == n ) cout << '\n' ;
		
	}
	
	for ( register int i = k ; i <= n ; i ++ )
	
	{
		cout << maxx [ i ] << ' ' ;
		
		if ( i == n ) cout << '\n' ;
		
	}
	
	return 0;
	
}