8846: [yosupo] Data Structure - Static Range LIS Query
[Creator : ]
Description
You are given permutation $P$ of $\lbrace 0, 1, \dots, N-1 \rbrace$.
Process the following $Q$ queries in order:
- $l$ $r$: Print the length of the longest increasing subsequence of $(P_l, P_{l+1}, \dots, P_{r-1})$.
Process the following $Q$ queries in order:
- $l$ $r$: Print the length of the longest increasing subsequence of $(P_l, P_{l+1}, \dots, P_{r-1})$.
Input
$N$ $Q$
$P_0$ $P_1$ $\cdots$ $P_{N-1}$
$l_0$ $r_0$
$l_1$ $r_1$
$\vdots$
$l_{Q-1}$ $r_{Q-1}$
$P_0$ $P_1$ $\cdots$ $P_{N-1}$
$l_0$ $r_0$
$l_1$ $r_1$
$\vdots$
$l_{Q-1}$ $r_{Q-1}$
Constraints
$1 \leq N \leq 100,000$
$1 \leq Q \leq 100,000$
$P$ is a permutation of $\lbrace 0, 1, \dots, N-1 \rbrace$
$0 \leq l_i \leq r_i \leq N$
$1 \leq Q \leq 100,000$
$P$ is a permutation of $\lbrace 0, 1, \dots, N-1 \rbrace$
$0 \leq l_i \leq r_i \leq N$
Sample 1 Input
4 3
0 2 1 3
0 2
0 4
1 3
Sample 1 Output
2
3
1