Bo2SS

Course Content#

Problem Introduction#

• $RMQ(x, y)$ function: Query the minimum value within the array $[x, y]$, refer to RMQ——OI Wiki
• If the end of the query interval is fixed, for example: $RMQ(x,7)$
  • At least the following 4 blue elements must be recorded to satisfy all requirements of $RMQ(x,7)$
  • 
  • And these 4 elements form a monotonically increasing sequence, which is also a monotonic queue
• The problem that the monotonic queue solves is maintaining the extreme values of such intervals [Fixed-end RMQ problem]

Monotonic Queue#

• The nature of the problem to be solved: Maintain the extreme value of the interval inside the sliding window
• Structure definition: Monotonic queue
• Structure operations
  • Enqueue: First eliminate the elements at the tail that violate monotonicity, then enqueue the current element
  • Dequeue: If the front element exceeds the range of the sliding window, dequeue the front
• The core of maintenance: Front element——the extreme value within the sliding window⭐
  • Minimum value → Increasing queue
  • Maximum value → Decreasing queue
• Amortized time complexity: O(1), solve once
• [PS] Another example to deepen the impression: The school selects student representatives to participate in the competition
  • 
  • Analogy: Grade -> Array index, Ability value -> Data value, Time period -> Sliding window
  • In the monotonic queue maintaining the maximum value of the interval [14-17], when you enqueue, Zhao Liu will be kicked out
    • Extension: If a person is younger than you and has stronger ability than you, then you will be kicked out forever

Monotonic Stack#

• Think about the difference between stack and queue, and the only difference between monotonic stack and monotonic queue lies here, other operations are the same [Enqueue, Dequeue]
  • 
  • Monotonic stack is a monotonic queue with one end blocked
  • Monotonic stack retains the enqueue operation of the monotonic queue, still maintaining monotonicity⭐
• Problem nature: Recent (greater than/less than) relationship
  • Before pushing onto the stack, the top element that meets monotonicity is the current pushed element's recent (greater than/less than) relationship
• The core of maintenance: Top element——recent (greater than/less than) relationship⭐
  • Left recent relationship → Left first push onto the stack
  • Right recent relationship → Right first push onto the stack
  • [PS] Its bottom is the global minimum value, but maintaining it with a stack is meaningless
• Amortized time complexity: O(1), solve once

Comparison of the Two#

In fact, the two are mainly different in form, but essentially similar

| |Open Port|Core Maintenance|Specialized Problems|Basic Operations|
|:----:|:----|:----:|:----|:----:|:----|:----:|:----|:----|
|Monotonic Queue|Front, Tail|Front|Extreme value of interval|Maintain monotonicity + Enqueue, Dequeue, Get Value|
|Monotonic Stack|Top|Top|Recent size relationship|Pop [Maintain monotonicity], Get Value, Push|

In-class Exercises#

——Introduction——#

HZOJ-261: Data Structure#

Sample Input

8
I 2
I -1
I 1
Q 3
L
D
R
Q 2

Sample Output

2
3

• Idea
  • Data scale: $1\le N\le 1000$
  • 
  • 【Key】 Analogous to the cursor operation of the terminal, maintain the position of the cursor⭐
  • 【Data Structure】 Two stacks s1, s2 corresponding to the cursor position [can also be simulated with arrays or linked lists]
  • 【Operation Analysis】
    • Insert: Push an element onto s1
    • Delete: Pop from s1
    • Move Left: Transfer the top element of s1 to s2
    • Move Right: Transfer the top element of s2 to s1
    • Query: Maintain a prefix sum array sum and a maximum prefix sum array ans, where ans stores the answer
  • [PS] If implemented with a single array, insertion is very time-consuming
• Code
  • 
  • 
  • Create a new data structure -> Structure definition + Structure operations
    • After defining the data structure, its methods can be easily used
  • Timing to maintain the prefix array sum and the maximum prefix sum array ans
    • When inserting elements into s1: Insert operation, Move right operation
    • Delete operation and move left operation also need to be maintained, but HZOJ's test samples have a BUG: The k value during the query, when greater than the cursor's current position [i.e., s1.size()], the answer still considers the maximum prefix sum from 1 to k, so it is necessary to retain the maximum prefix sum corresponding to each position in s2
  • [PS]
    • The 0th position of the sum and ans arrays needs to retain an initial value for initial prefix sum accumulation and comparison
    • The data in ans is only responsible for comparison, not for calculation; the data in sum is only responsible for calculation, not for comparison
    • The k input for the query operation may be larger than the total length, so it can also be specially treated to return the overall maximum prefix sum

HZOJ-263: Train Stacking#

Sample Input

3

Sample Output

123
132
213
231
321

• Idea
  • Note the problem statement: 1~n enters the station in order; output the first 20 answers
  • First think about whether 312 will appear in the sample output?
    • If you want to get 3 first, you need to push 1 and 2, so the only way to pop is 321
  • 【Key】 Determine whether the sequence in the full permutation is valid
  • Assume that the maximum train number that has already entered the stack is $x$; the current number to be popped in a permutation sequence is $y$
    • If $y ≤ x$, it means $y$ must be the top element of the stack, otherwise the sequence is invalid
    • If $y > x$, push all elements in $[x + 1,\ y]$ onto the stack, at this point the top element must be y
    • For example: Check if 4132 and 3241 are valid?
      • 
      • Note the comparison of $x$ and $y$, $x$ can only increase or remain unchanged, not decrease
      • You can simulate it yourself
• Code
  • 
  • Pay attention to the clever use of the top pointer in the stack and the maximum value currently being pushed onto the stack [Simulated with an array]
  • The judgment of top == -1 is for generality, which will not exist here
  • Use the function bool next_permutation(begin, end) to get the next permutation [in lexicographical order], the return value indicates whether there is a next permutation
    • 
    • Refer to cplusplus

——Monotonic Queue——#

HZOJ-271: Sliding Window#

Sample Input

8 3
1 3 -1 -3 5 3 6 7

Sample Output

-1 -3 -3 -3 3 3
3 3 5 5 6 7

• Idea
  • Data scale: $1\le N \le 300000$
  • Pure monotonic queue, focus on code implementation
• Code
  • 
  • 
  • Consider: Should the monotonic queue record values or record indices
    • Record indices🆒, because with indices you can index to values [following the clues]
    • Recording values, however, cannot be traced back
  • This is a commonly used monotonic queue template: Maintain monotonicity → Enqueue → Dequeue → Output according to the problem
  • Focus on maximum/minimum values and the size of the window
  • [PS] The tail can both enqueue and dequeue [kick out, maintain monotonicity], so it is not considered a unidirectional queue

HZOJ-372: Twin Sequences#

Sample Input

5
3 1 5 2 4
5 2 4 3 1

Sample Output

4

• Idea
  • Think: What does it mean for two sequences to have the same trend?
    • The RMQ values within the same interval are the same, ❗ here RMQ value → the maximum index of the minimum value
  • 【Key】 The RMQ values of each interval of the two sequences are equal 👉 the monotonic queues of the two sequences look the same
    • In other words, at every moment, the two sequences correspond to the same monotonic queue
    • Note: Looking the same refers not to the minimum value, but to the corresponding indices [the monotonic queue stores indices]
  • Insert the elements of the two sequences into the monotonic queue one by one, and compare the size of the monotonic queue after each insertion
    • ① If they are the same, continue to enqueue
    • ② If they are not the same, output the answer
• Code
  • 
  • 
  • Use class to define monotonic queue for easy reuse
  • The monotonic queue stores indices: p
  • Monotonic queue operations: Maintain → Enqueue, no need to dequeue
  • 【Clever】 Grasp trend changes based on the size changes of the queue

HZOJ-270: Maximum Subarray Sum#

Sample Input

6 4
1 -3 5 1 -2 3

Sample Output

7

• Idea
  • Subarray sum → Interval sum, can be obtained using prefix sum
  • Limited condition: The length of the subarray does not exceed $m$ → Sliding window
  • Therefore, it is converted into a problem on the prefix sum array
    • 
    • Target: $max_j{s_i-s_j}\ |\ 0\lt i-j\le m$, that is, find the smallest $s_j$, to get $max_j{Sum_{j+1}^i}$
      • $s_i$ represents the sum of the first $i$ elements of the original sequence
  • 【Problem Transformation】
    • Maintain the minimum value of a sliding window of size $m$ on the prefix sum array $s$
  • 👉 Monotonic queue. Note: The maintenance is not on the original sequence, but on the prefix sum array
• Code
  • 
  • Monotonic queue operations: Dequeue → Get Value → Maintain monotonicity + Enqueue
    • The original routine is to maintain monotonicity + Enqueue first, that is, the dequeue and get value operations are placed later [this is fine]
    • But changing the order is also possible: Because the window size $m\ge1$, the last element in the queue is at least not used, so placing the get value operation first will not miss any value
    • [PS] The dequeue operation only needs to be before the get value
  • Only the prefix sum information is needed, the original information does not need to establish an array
  • ❗ For interval sum queries, do not forget the significance of the 0th element of the prefix sum array, remember to push it into the monotonic queue initially

——Monotonic Stack——#

HZOJ-264: Maximum Rectangle Area#

Sample Input

7
2 1 4 5 1 3 3

Sample Output

8

• Idea
  • Think: The property of the maximum rectangle ——> Rectangle height = height of the shortest board in the area x
    • If the rectangle height > x, it cannot form a rectangle
    • If the rectangle height < x, why can't it be = x?
  • Specific idea
    • Conversely, determine the current rectangle height based on a certain board, find the first height smaller than it to the left and right, and the area in between is the maximum rectangle area it can obtain
    • Then traverse each board to find the maximum area obtained, taking the maximum value
  • Need to solve: The recent position of the height less than the current board for each board, so use [monotonic stack]
  • [Inspiration] Analyzing the properties of the optimal solution is the first step to solving the problem
• Code
  • 
  • 
  • The data that needs to be stored in the array includes: board height data, monotonic increasing stack, storing left/right recent minimum
  • Pay attention to the boundary handling skills: Set extremely small boards [-1] at both ends, and initialize the stack bottom to the index of the extremely small board [0, n + 1]
  • Finally, integrate the left/right to calculate the area and take the maximum
  • This is also a commonly used monotonic stack template: Maintain monotonicity [Pop] → Get value according to the problem → Push
  • Sample analysis:
    • 
    • Note that the monotonic stack stores index values

Tips#

• For dynamic programming problems related to monotonic queues/stacks, please jump to: 2 From Recursion to Dynamic Programming (Part 2)