## CBOJ 2022 Spring Contest Problem 4 - Allen's Automata

Points: 15 (partial)
Time limit: 1.0s
C++ 0.5s
Java 8 2.0s
Python 5.0s
Memory limit: 512M

Author:
Problem type

As a member of the Bolonel Cy robotics club, allentao loves robots!

In fact, he loves them so much that he has $$N$$ robots in a line, each with a weight $$w_{i}$$. He also has $$Q$$ requests, each of which are one of the following:

• U x y: Update the weight of robot $$x$$ to $$y$$ ($$w_{x} := y$$).
• Q1 L R: Query the minimum weight of all robots in the range of indices $$[L, R]$$.
• Q2 L R: Query the maximum weight of all robots in the range of indices $$[L, R]$$.
• Q3 L R X Y: Determine whether or not the sequences $$w_{[L, R]}$$ and $$w_{[X, Y]}$$ are equivalent.

Being not only a robotics prodigy, but a legendary programmer, allentao instantly solved the problem.

To ensure the correctness of his solution, he poses the problem to Zeyu. However, Zeyu has been spending his time studying Orz Trees, so he hasn't a clue how to solve it! Desperately, Zeyu comes to you for assistance. Can you help him?

#### Input Specification

The first line contains two space separated integers: $$N$$, denoting the number of robots, and $$Q$$, the number of requests.

The second line contains $$N$$ space separated integers $$w_{i}$$, the $$i$$-th of which denotes the weight of the $$i$$-th robot.

The next $$Q$$ lines each have a query of the above format.

#### Output Specification

For Q1, output the minimum weight of all robots in the range of indices $$[L, R]$$.

For Q2, output the maximum weight of all robots in the range of indices $$[L, R]$$.

Finally, for Q3, output YES if $$w_{[L, R]} = w_{[X, Y]}$$, otherwise output NO.

#### Input Constraints

$$1 \le N, Q \le 10^{5}$$

$$1 \le w_{i} \le 10^{9}$$

$$1 \le x_{i} \le N$$

$$1 \le y_{i} \le 10^{9}$$

$$1 \le L_{i} \le R_{i} \le N$$

$$1 \le X_{i} \le Y_{i} \le N$$

$$N, Q \le 10^{3}$$

There will be no Q3 queries.

#### Sample Input 1

5 4
1 2 3 2 2
U 1 2
Q1 1 3
Q2 2 3
Q3 1 2 4 5

#### Sample Output

2
3
YES

#### Explanation for Sample Input

The first request changes the array of robots from $$[1, 2, 3, 2, 2]$$ to $$[\textbf{2}, 2, 3, 2, 2]$$

The second request is the minimum value of the range $$[1, 3]$$. This is $$min(w_{1}, w_{2}, w_{3}) = min(2, 2, 3) = 2$$.

The third request is the maximum value of the range $$[2, 3]$$. This is $$max(w_{2}, w_{3}) = max(2, 3) = 3$$.

The fourth, and final, request is to report whether or not $$w_{1, 2} = w_{4, 5}$$. Since $$[w_{1}, w_{2}] = [2, 2]$$ and $$[w_{4}, w_{5}] = [2, 2]$$, these two sequences are equal. Therefore, we print YES.