Monotonic Queue Template

Zhiyuan Xu Lv1
  2024-07-06 00:10:40 2024-07-06 00:10:40 Created   2024-07-06 00:10:51 2024-07-06 00:10:51 Updated   
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
namespace Monotonic_queue{
  inline void solve_max(){
    tail = 0;head = 1;
    q[0] = -1e9;
    For(1,n,1){
      while(tail>=head && pos[i]>=pos[q[tail]]) tail--;
      while(q[head]<=i-k && head<=tail) head++;
      q[++tail] = i;
      if (i>=k) write(pos[q[head]]),putchar(' ');
    }
    cout << endl;
  }
  inline void solve_min(){
    tail = 0;head = 1;
    q[0] = 1e9;
    For(1,n,1){
      while(tail>=head && pos[i]<=pos[q[tail]]) tail--;
      while(q[head]<=i-k && head<=tail) head++;
      q[++tail] = i;
      if (i>=k) write(pos[q[head]]),putchar(' ');
    }
    cout << endl;
  }
}
  • Title: Monotonic Queue Template
  • Author: Zhiyuan Xu
  • Created at : 2024-07-06 00:10:40
  • Updated at : 2024-07-06 00:10:51
  • Link: https://redefine.ohevan.com/Template/MonoQueue/
  • License: This work is licensed under CC BY-NC-SA 4.0.
Comments
On this page
Monotonic Queue Template