P3865 [Template] ST Table & RMQ Problem

This is a classic ST table problem — static range maximum. Please note that the maximum time limit for the largest testdata is only 0.8 s, and the data is not weak. Please ensure that the time complexity per query is $O(1)$. If you use a higher time complexity algorithm, it is not guaranteed to pass. If you believe your code has the correct time complexity but gets TLE, you can try fast input: ```cpp inline int read() { int x=0,f=1;char ch=getchar(); while (ch'9'){if (ch=='-') f=-1;ch=getchar();} while (ch>='0'&&ch

Given a sequence of length $N$ and $M$ queries, for each query, find the maximum number in the specified interval.

The first line contains two integers $N, M$, representing the length of the sequence and the number of queries. The second line contains $N$ integers (denoted as $a_i$), representing the $i$-th element of the sequence in order. The next $M$ lines each contain two integers $l_i, r_i$, indicating that the query interval is $[l_i, r_i]$.

Output $M$ lines, each containing one integer, representing the answer to each query in order.

- For 30% of the testdata, $1 \le N, M \le 10$. - For 70% of the testdata, $1 \le N, M \le {10}^5$. - For 100% of the testdata, $1 \le N \le {10}^5$, $1 \le M \le 2 \times {10}^6$, $a_i \in [0, {10}^9]$, $1 \le l_i \le r_i \le N$. Translated by ChatGPT 5