单调队列

发表于 更新于 分类于

模拟双端队列

初始化：

1
hh = 1 , tt = 0;

入队：

1
2
q[++tt] = i
q[--hh] = i

出队

1
2
tt--
hh++

判断是否队列非空

1
if(tt>=hh)

滑动窗口

题目描述：

有一个长为 \(n\) 的序列 \(a\)，以及一个大小为 \(k\) 的窗口。现在这个从左边开始向右滑动，每次滑动一个单位，求出每次滑动后窗口中的最大值和最小值。

例如，对于序列 \([1,3,-1,-3,5,3,6,7]\) 以及 \(k = 3\)，有如下过程：

\[\def\arraystretch{1.2} \begin{array}{|c|c|c|}\hline \textsf{窗口位置} & \textsf{最小值} & \textsf{最大值} \\ \hline \verb![1 3 -1] -3 5 3 6 7 ! & -1 & 3 \\ \hline \verb! 1 [3 -1 -3] 5 3 6 7 ! & -3 & 3 \\ \hline \verb! 1 3 [-1 -3 5] 3 6 7 ! & -3 & 5 \\ \hline \verb! 1 3 -1 [-3 5 3] 6 7 ! & -3 & 5 \\ \hline \verb! 1 3 -1 -3 [5 3 6] 7 ! & 3 & 6 \\ \hline \verb! 1 3 -1 -3 5 [3 6 7]! & 3 & 7 \\ \hline \end{array} \]

输出共两行：

第一行为每次窗口滑动的最小值，第二行为每次窗口滑动的最大值。

思路：

例如针对最小值：队列中存放的是当前窗口可能最小值的下标，并且保证队列中下标对应的保持单调递增，这样队首的下标对应的值，即为当前窗口的最小值。

需要维护两个问题：

  1. 当前下标与队首下标的差值大于等于\(k\)，则表示队首和队尾已经不在一个窗口当中，这时需要把队首弹出。
  2. 当前数小于队列尾下标对应的数时，可以弹出队尾。因为从当前数a[i]进入窗口开始，到队列尾数a[q_tt]离开窗口为止，窗口始终包含a[i]，因此最小值一定不可能为比a[i]大的数a[q_tt]，因此将队列尾弹出可以减少时间复杂度。
  3. 当前窗口的最小值始终为：\(a[q\_hh]\)

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include<iostream>
using namespace std;

const int N = 1000005;

int n,k;
int a[N],q[N];
int tt,hh;

void out_min_deque()
{
    hh = 1 , tt = 0;
    for(int i=1;i<=n;i++)
    {
        while(tt>=hh && i-q[hh]>=k) hh++;
        while(tt>=hh && a[i]<a[q[tt]]) tt--;
        q[++tt] = i;

        if(i>=k) cout<<a[q[hh]]<<" ";
    }
}

void out_max_deque()
{
    hh = 1 , tt = 0;
    for(int i=1;i<=n;i++)
    {
        while(tt>=hh && i-q[hh]>=k) hh++;
        while(tt>=hh && a[i]>a[q[tt]]) tt--;
        q[++tt] = i;

        if(i>=k) cout<<a[q[hh]]<<" ";
    }
}

int main()
{
    cin>>n>>k;

    for(int i=1;i<=n;i++) cin>>a[i];

    out_min_deque();

    cout<<endl;

    out_max_deque();

    return 0;
}

寻找段落

题目描述

给定一个长度为 \(n\) 的序列 \(a\)，定义 \(a_i\) 为第 \(i\) 个元素的价值。现在需要找出序列中最有价值的“段落”。段落的定义是长度在 \([S, T]\) 之间的连续序列。最有价值段落是指平均值最大的段落。

段落的平均值 等于 段落总价值 除以 段落长度。

思路

  1. 找平均值最大的一个段落 可以转换为二分答案，\(s[i] = s[i-1] + a[i] - mid\)，若存在一段区间和大于0，则段落平均值的最大值一定大于\(mid\)。因此问题转化为寻找最大区间和问题，找到一个区间和大于0的区间，即可有效。
  2. 对于一个区间\([l,r]\)来说，区间和为前缀和之差\(a[r]-a[l-1]\)。当我们确定右端点\(r\)时，只需在\([r-t+1,r-s+1]\)范围内选取一个\(l\)，找到\(a[l-1]\)最小值，即可找到区间最大值。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include<iostream>
using namespace std;

const int N = 1000005 , INF = 10000;

int n,s,t;
int a[N];
double b[N];
int q[N],tt,hh;

bool check(double x)
{
    hh = 1 , tt = 0;
    for(int i=1;i<=n;i++)
        b[i] = b[i-1] + a[i] - x;

    // for(int i=s,j=0;i<=n;i++,j++)
    // {
    //     //i为区间尾,这里找从1~j的最小区间和
    //     while(tt>=hh && b[j]<b[q[tt]]) tt--;
    //     q[++tt] = j;

    //     while(tt>=hh && i-q[hh]>t) hh++;

    //     if(b[i] - b[q[hh]] > 0.00001) return true;
    // }

    for(int i=1;i<=n;i++)
    {
        if(i>=s)
        {
            while(tt>=hh && b[i-s]<b[q[tt]]) tt--;
            q[++tt] = i-s;
        }

        while(tt>=hh && i-q[hh]>t) hh++;

        if(tt>=hh && b[i]-b[q[hh]]>0) return true;

    }

    return false;
}

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

    double l = -INF , r = INF;
    while(r-l > 1e-4)
    {
        double mid = (r+l) / 2;
        if(check(mid)) l = mid;
        else r = mid;
    }

    printf("%.3f",l);

    return 0;
}

ST表 || RMQ

该类问题为求：查询区间的最大值或最小值，思路用到了倍增思想。

设\(f[i][j]\)为从\(i\)开始的\(2^j\)个数中的最大值，可以从短到长合并，求得所有\(f[i][j]\)

最后查询区间，只需查询\(max(f[l1][k],f[l2][k])\)。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include<iostream>
#include<math.h>
using namespace std;

const int N = 100005;

int n,m;
int a[N],f[N][20];
int l,r;

inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}

int query(int l,int r)
{
    int k = log2(r-l+1);
    return max(f[l][k],f[r-(1<<k)+1][k]);
}

int main()
{
    n = read();
    m = read();

    for(int i=1;i<=n;i++) a[i] = read();
    for(int i=1;i<=n;i++) f[i][0] = a[i];

    for(int i=1;i<=20;i++)
        for(int j=1;j<=n;j++)
        {
            int r2 = j + (1<<i) - 1;
            int l2 = j + (1<<(i-1));
            if(r2>n) break;

            f[j][i] = max(f[j][i-1],f[l2][i-1]);
        }

    for(int i=1;i<=m;i++)
    {
        l = read();
        r = read();
        printf("%d\n",query(l,r));
    }

    return 0;
}

良好的感觉

题目描述

kkk 做了一个人体感觉分析器。每一天，人都有一个感受值 \(A_i\)，\(A_i\) 越大，表示人感觉越舒适。在一段时间 \(\left[i, j\right]\) 内，人的舒适程度定义为 \(\left[i, j\right]\) 中最不舒服的那一天的感受值 \(\times\) \(\left[i, j\right]\)中每一天感受值的和。现在给出 kkk 在连续 \(N\) 天中的感受值，请问，在哪一段时间，kkk 感觉最舒适？

思路

单调栈：给定一个序列，求每个元素在其后第一个大于他的元素下标。可以从后往前跑一遍，将小于等于他的元素出栈，此时栈顶的下标即为第一个大于他的元素。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include<iostream>
using namespace std;

const int N = 1000005;
#define int long long

int n;
int a[N],s[N];
int l[N],r[N];
int stk[N],hh,tt;
int ans;

signed main()
{
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=n;i++) s[i] = s[i-1] + a[i];

	tt = -1;
	for(int i=1;i<=n;i++)
	{
		while(tt>=0 && a[i]<=a[stk[tt]]) tt--;

		if(tt>=0) l[i] = stk[tt];
		else l[i] = 0;

		stk[++tt] = i;
	}

	tt = -1;
	for(int i=n;i>=1;i--)
	{
		while(tt>=0 && a[i]<=a[stk[tt]]) tt--;

		if(tt>=0) r[i] = stk[tt];
		else r[i] = n+1;

		stk[++tt] = i;
	}

	for(int i=1;i<=n;i++)
	{
		int sum = a[i] * (s[r[i]-1]-s[l[i]]);
		ans = max(ans,sum);
	}

	cout<<ans<<endl;

	return 0;
}