单调队列思想与方法总结

总结

单调队列：队列指的是双端队列，而单调指的是队列具有单调性。

单调队列和单调栈非常相像，但是侧重点不同，一种的强调大小，在弹出的时候计算结果(盖棺定论)或者计算贡献，在弹出的时候终结贡献。而单调队列，侧重点则在于值中。我们通过维持一定范围内的最大值与最小值，来进行接下来项目的计算，直到计算出答案。单调队列的重点，就在于一定范围的维持，和怎么与动态规划如何结合,同时，为了范围计算的方便，我们往往在队列中存储下标。

最基础板子

P1886 滑动窗口 /【模板】单调队列

计算范围为 $ k $ 的最小值和最大值，最基础的模板，单调队列的运作，就像是打ACMer一样。

如果最强的选手到了退役的年纪，那么就该退役了(弹出头部)。
如果出现了一个又强又新的新人，他就可以把比他弱的老人给顶替掉(弹出尾部)。

(有时候，因为我们的计算问题，我们最好手动添加节点，方便之后的计算)

我们根据这个逻辑，去写出最小值，接下来将值取成负数再求一次即可。

 int n ; cin >> n ; 
int k ; cin >> k ;  
vector<int>a(n+1) , ans(n + 1 ); 
for(int i = 1 ; i <= n ; i++)cin >> a[i] ; 
const auto calc =[&](){
   deque<int> q ; 
   for(int i = 1;  i<= n  ; i++){
      while(!q.empty() && i - q.front() + 1 > k)q.pop_front() ;  
      while(!q.empty() && a[q.back()] > a[i])q.pop_back()   ; 
      q.push_back(i) ; 
      if(i >= k)ans[i-k+1] = q.front() ; 
   }
};
calc() ; 
for(int i = 1; i<= n - k + 1 ; i++)cout << a[ans[i]] << ' '; 
cout << '\n' ; 
for(int i = 1; i<= n   ; i++)a[i] = -a[i] ; 

calc() ; 
for(int i = 1;  i<= n- k + 1  ; i++)cout << -a[ans[i]] << ' ' ;

与dp的结合

题目描述

数列 ${p_n}$ 中，找出一个子段 $[l,r](r-l+1\le m)$，最大化 $\sum\limits_{i=l}^rp_i$。

这一题我们可以想到我们可以使用前缀和去优化计算，我们可以考虑去计算以每一个 $ i $ 为结尾的最大值，当然了。我们既然要维护，就给每一个都算，既然我们需要维护这样子的最大值，所以队列里的值最好越小越好(所以我们就维护递减的单调队列即可)

int n , k ; cin >>n >> k ;
vector<int>a(n+1) ;
vector<i64>pre(n+1) ; 
int ans = -inf ;  
for(int i = 1 ; i<= n ; i++){
   cin >> a[i] ;
   pre[i] = pre[i-1] + a[i] ;  
   ans = max(ans , a[i]) ; 
} 
int sum = 0 ;
deque<int> q ; 
q.push_back(0) ; 
for(int i = 1; i<= n ; i++){
   while(!q.empty() && i - q.front()  > k ){
      q.pop_front() ; 
   }
   ans = max(1ll*ans , pre[i] - pre[q.front()] ) ; 
   while(!q.empty() && pre[q.back()]>= pre[i] ){
      q.pop_back();
   }
   q.push_back(i) ; 

} 
cout << ans << '\n' ;

P12882 [蓝桥杯 2025 国 C] 数列染色

一个长度为 $ n $ 的数组, $ a_1 $ 与 $ a_n $ 已经染黑，相邻两点最多包含 $ k $ 个白色的数，求所有黑色数之和。

这里依旧我们注意到，每两个数间隔最多为 $ k $ ，就可以直到，一个数的生命周期最长也就 $ k $ 了，以此我们写下代码。

当然，因为我们 $ dp_i $ 是通过之前的转移过来，所以我们手动计算 $ dp_1 $ 防止边界情况。

int n ; cin >> n ;
int k ; cin >> k ;  
vector<i64>a(n+1) , dp(n+1, lnf ) ;
for(int i = 1 ; i<= n ; i++)cin >> a[i] ;  
i64 ans = lnf ; 
deque<int>q ; 
dp[1] = a[1] ; 
q.push_back(1) ; 
for(int i = 2; i<= n ; i++ ){
   while(!q.empty() && i - q.front() - 1 > k )q.pop_front() ; 
   dp[i] =dp[q.front()] + a[i]  ;
   while(!q.empty() && dp[q.back()] > dp[i])q.pop_back() ; 
   q.push_back(i) ; 
}
cout << dp[n] << '\n' ;

P1725 琪露诺

这一题，相比于之前的题增加了更多的限制，我们只能从区间 $ [i+L,i+R] $中的任意一格中转移，就代表我们压入的数据并不能直接转移，仔细想想，如果直接整了，是不是很不双端队列，所以我们换个思维，直接从 $ L $ 点出发，每一次只把 $ i - L $ 压入队列，这样我们就解决了这个问题，其它就正常写即可。


int n , L,  R ; cin >> n>> L >> R ; 
vector<int>a(n+1) , dp(n+1 , -inf) ; 
for(int i =0 ; i<= n ; i++)cin >> a[i] ;
dp[0] = a[0] ; 
deque<int> q ; 
q.push_back(0) ; 
int ans = -inf ; 
for(int i = L ; i<= n ; i++){
  while(!q.empty() && q.front() < i - R )q.pop_front() ; //维持 l - n的数列，此刻是连续的
  while(!q.empty() && dp[q.back()] < dp[i-L])q.pop_back() ; 
  q.push_back(i - L) ; //=增加转移
  dp[i] = dp[q.front()] + a[i] ; 
  if(i + R > n )ans =max(ans , dp[i]) ;  
} 

cout << ans << '\n'

P9691 [GDCPC 2023] Base Station Construction

这一题，我们有一个长度为 $ n $ 的数组，我们需要满足 $ m $ 个需求，需求即使在 $ l_i $ 到 $ r_i $ 之间必须满足选上一个，求满足所有需求的最小值。

我们思考一下，我们可以发现，如果我们在 $ i $ 的地方，我们必须要从可以满足 $ i-1 $ 所要求的需求，只要满足了，我们就可以进行一个寻找最小值的转移，这就和单调队列并无区别了。

那么我们该怎么满足需求呢？同样，我们从生命周期入手，增添一个需求，就代表我们的生命周期得到了限制，一开始我们可以从任意地方进行转移，然后逐渐限制，这种限制是逐渐靠近 $ R $ 的，所以我们对每一个 $ R $ 的需求求个 $ max $。并且求前缀最大值(因为对于每一个 $ i $ 都给满足这些要求)。

当然，我们生命周期总不可能是 $ 1 $ 吧，转到这就不能转了？所以我们要给每一个 $ r+1 $

int n ; cin >> n ;
vector<i64>a(n+2) , dp(n+2), pre(n+2); 
for(int i = 1; i<= n ; i++)cin >> a[i] ; 
int m ; cin >> m ; 
for(int i = 1; i<= m ; i++){
  i64 l , r ; cin >> l >> r ; 
  pre[r+1] = max(pre[r+1] , l) ; //要是想要满足条件，就需要
}

pre[1] = 0 ;
for(int i =2 ; i<= n + 1  ;i++)pre[i] = max(pre[i-1] ,pre[i]) ; 
deque<i64> q;
q.push_back(0) ;
for(int i = 1 ; i<= n + 1  ;i++){
  while(!q.empty() && q.front() < pre[i])q.pop_front() ; 
  dp[i] = dp[q.front()] + a[i] ; 
  while(!q.empty() && dp[q.back()] >= dp[i])q.pop_back() ; 
  q.push_back(i) ; 
}
cout << dp[n + 1 ] << '\n' ;

我们有一个 $ n \times m $ 的数组，对于每一个 $ i $ 要求长度为 $ m $ 的网格，我们要求从 $ 1-n $ 安装桥墩，$ 1 $ 和 $ m $ 必须安装桥墩 ,并且每过 $ d $ 个距离必须安装桥墩。距离公式为 $ d = |j_1 - j_2| - 1 $，价格计算为 $ a_{i,j} + 1$。我们要在连续个 $ k $ 行分别进行这些操作，并且使得总价格最小。

生命周期已经给出来了，我们只需要对每一行都进行单调队列处理，然后前缀和枚举求值即可。

int n , m , k , d ; cin >> n >> m >> k  >> d ; 
vector<vector<i64>>a(n+1 , vector<i64>(m+1)) ; 
vector<i64>dp(m+1), pre(n+1); 

for(int i = 1;  i<= n ; i++){
  for(int j = 1;  j <= m ; j++){
    cin >> a[i][j] ; 
  }
}
for(int i =1 ;i<= n ; i++){
  deque<int>q ; 
  dp[1] = 1 ;  
  q.push_back(1) ; 
  for(int j = 2 ; j<= m ; j++){
    while(!q.empty() && q.front() < j - d - 1 )q.pop_front() ; 
    dp[j] = dp[q.front()] + a[i][j] + 1  ; 
    while(!q.empty() && dp[q.back()] > dp[j])q.pop_back() ; 
    q.push_back(j) ; 
  }
  pre[i] = pre[i-1] + dp[m] ; 
}
i64 ans = lnf ; 
for(int i = k ; i<= n ; i++){

  ans = min(ans , pre[i] - pre[i-k]) ; 
}
cout << ans << '\n' ;

单调队列思想与方法总结