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 record the following 4 blue elements 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 values of the interval within the sliding window
• Structure definition: Monotonic queue
• Structure operations
  • Enqueue: First eliminate 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 element
• 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, then you will always be kicked out

Monotonic Stack#

• Think about the difference between stacks and queues, and the only difference between monotonic stacks and monotonic queues lies here, other operations are the same [Enqueue, Dequeue]
  • 
  • A monotonic stack is a monotonic queue with one end blocked
  • The monotonic stack retains the enqueue operation of the monotonic queue, still maintaining monotonicity⭐
• Nature of the problem: 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 side pushed first
  • Right recent relationship → Right side pushed first
  • [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, Back|Front|Extreme values of intervals|Maintain monotonicity + Enqueue, Dequeue, Get Value|
|Monotonic Stack|Top|Top|Recent size relationships|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 in the terminal, maintain the position of the cursor⭐
  • 【Data Structure】 Double stack, the tops of two stacks s1 and s2 correspond to the cursor position [can also be simulated with an array or linked list]
  • 【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 just one 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 for maintaining 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 handled to return the overall maximum prefix sum

HZOJ-263: Train Stack#

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 there will be 312 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 that $y$ must be the top element of the stack, otherwise the sequence is invalid
    • If $y > x$, push all elements from $[x + 1,\ y]$ onto the stack, at this point the top element of the stack must be y
    • For example: Check if 4132 and 3241 are valid?
      • 
      • Pay attention to the comparison of $x$ and $y$, $x$ can only increase or remain unchanged, not decrease
      • You can simulate it once
• 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 back of the queue 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 → 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 consistent, continue to enqueue
    • ② If they are inconsistent, 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 the 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
  • Limiting condition: The length of the subarray does not exceed $m$ → Sliding window
  • Therefore, it is transformed into a problem on the prefix sum array
    • 
    • Goal: $max_j{s_i-s_j}\ |\ 0\lt i-j\le m$, that is, find the minimum $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】
    • On the prefix sum array $s$, maintain the minimum value of a sliding window of size $m$
  • 👉 Monotonic queue. Note: Maintaining not the original sequence, but the prefix sum array
• Code
  • 
  • Monotonic queue operations: Dequeue → Get value → Maintain monotonicity + Enqueue
    • The usual routine is to maintain monotonicity + Enqueue first, that is, the Dequeue and Get value operations are placed later [this is fine]
    • But switching the order is also possible: because the window size $m\ge1$, the last element in the queue is at least not needed, so placing Get value first will not miss any values
    • [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 initially push it into the monotonic queue

——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 equal x?
  • Specific idea
    • Conversely, determine the height of the current rectangle based on a certain board, find the first height smaller than it to the left and right, 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 nearest height less than the current board's height 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 nearest minimum
  • Pay attention to the boundary handling technique: Set extremely low heights [-1] at both ends, and initialize the stack bottom to the index of the extremely low height 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)