2023 USP Try-outs |
---|
Finished |
Every Brazilian knows Ryan Ochoa very well, the Mexican goalkeeper who park the bus the goal against Brazil in the 2014 World Cup. More than that, the guy becomes the best goalkeeper in history during any World Cup period and hibernates for the following 4 years. What nobody knows is that in reality, he is training his successor as the best goalkeeper in World Cups: you! Now you need to buy one pair for yourself and one pair for Ochoa. In the store, there are exactly $$$N$$$ gloves on display, arranged in a line. The glove in position $$$i$$$ has size $$$A_i$$$. The size you both wear doesn't matter, as you are the best in the world in your position. However, to not hinder the performance in training, it's crucial to choose the same size $$$X$$$ for both your gloves and the same size $$$Y$$$ for Ochoa's ($$$X$$$ and $$$Y$$$ can be different). Every day, the gloves available for sale can change! They are always defined by an interval $$$[l, r]$$$ that represents the positions of the gloves for sale at that moment. Moreover, the glove at position $$$i$$$ can be replaced by another of a different size. We have $$$Q$$$ changes in total, and they are described as follows:
The first line contain two integers $$$n$$$ and $$$q$$$ ($$$1 \leq n, q \leq 10^5$$$).
The second line contains a sequence $$$A_i$$$ of size $$$n$$$ ($$$1 \leq A_i \leq 10^9$$$).
The next $$$q$$$ lines contains the operations described in the statement.
For each operation of type $$$1$$$:
4 3 1 1000000000 1 1 1 1 4 0 4 1000000000 1 1 4
-1 2 4 1 3
10 8 1 1 2 3 4 5 5 6 7 10 1 1 6 1 1 7 0 4 2 1 1 6 0 1 5 1 1 6 0 4 3 1 1 7
-1 6 7 1 2 3 4 1 2 1 6 3 4 -1
Name |
---|