A Decreasing Stack with Point Updates¶
Time limit: 0.5 seconds. Memory limit: 256 MiB. See the reference environment and measurements.
Story¶
An observation station records signal strengths by position. During playback, a new signal removes all top signals that are no stronger. Records can be corrected, and the station needs the number of signals left after each playback.
(This story was rewritten by GPT-6.)
Formal Problem Statement¶
Given an integer sequence \(a\) of length \(n\) , process \(m\) operations:
1 x v: set \(a_x=v\) .2 l r: start with an empty stack and insert \(a_l,a_{l+1},\ldots,a_r\) in that order. Before pushing a value \(v\) , pop while the stack is nonempty and its top is \(\le v\) . Print the final stack size.
Queries do not change the sequence. Indices start at \(1\) , and each query starts with a fresh stack. Equal values cause a pop, so values from bottom to top are strictly decreasing.
Input Format¶
The first line contains n m . The second contains the \(n\) initial values. Each of the next \(m\) lines contains one operation above.
Output Format¶
Print one integer on its own line for each query.
Sample 1¶
Input¶
5 6
5 3 3 4 2
2 1 5
1 1 1
2 1 5
2 2 3
1 3 8
2 2 5
Output¶
3
2
1
3
Sample 2¶
Input¶
1 3
0
2 1 1
1 1 1000000000
2 1 1
Output¶
1
1
Sample Explanation¶
The first query of Sample 1 leaves \([5,4,2]\) . Updating the first value leaves \([4,2]\) ; querying the two equal values \(3\) leaves one value.
Insert from left to right; a later value at least as large removes an earlier value.
Constraints and Scoring¶
\(1\le n,m\le50000\) , \(0\le a_i,v\le10^9\) , \(1\le x\le n\) , and \(1\le l\le r\le n\) .
Specifications redesigned by Codex (GPT-6): the traversal direction, popping on equality, and independent query stacks.
| Score | Additional constraints |
|---|---|
| 20% | \(n\le50,\ m\le100\) |
| 30% | \(n,m\le2000\) |
| 50% | No additional constraints |