单调队列

模拟双端队列

初始化:

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;
}