內容
一個大小為 $N$ 數列 $A$ 的 LIS 是這個數列中最長遞增的子序列，也就是一個最大的 $k$ 使得 $1\leq i_1<i_2<\dots <i_k\leq N, A_{i_1}<A_{i_2}<\dots<A_{i_k}$。
給你一個大小為 $n$ 的數列 $a$，共 $q$ 個詢問，每個詢問給你 $l, r$，請你求出 $a_l\sim a_r$ 的 LIS 大小是多少？
輸入說明
第一行輸入兩個正整數 $n,q$，代表陣列大小與詢問次數。
第二行輸入 $n$ 個正整數 $a_1\sim a_n$。
接下來 $q$ 行，每行輸入兩個正整數 $l, r$。
- $1\leq n,q\leq 10^5$
- $1\leq a_i\leq 10^9$
- $1\leq l\leq r\leq n$
輸出說明
對於每筆輸入，請你輸出 $a_l\sim a_r$ 的 LIS 大小是多少。
範例輸入
#1
5 5 2 5 3 1 4 3 5 2 4 1 4 4 4 2 3
範例輸出
#1
2 1 2 1 1
測資資訊：
記憶體限制：
128
MB
公開 測資點#0 (10%): 3.0s , <1M
公開 測資點#1 (10%): 3.0s , <10M
公開 測資點#2 (10%): 3.0s , <10M
公開 測資點#3 (10%): 3.0s , <10M
公開 測資點#4 (10%): 3.0s , <10M
公開 測資點#5 (10%): 3.0s , <10M
公開 測資點#6 (10%): 3.0s , <10M
公開 測資點#7 (10%): 3.0s , <10M
公開 測資點#8 (10%): 3.0s , <10M
公開 測資點#9 (10%): 3.0s , <10M
公開 測資點#0 (10%): 3.0s , <1M
公開 測資點#1 (10%): 3.0s , <10M
公開 測資點#2 (10%): 3.0s , <10M
公開 測資點#3 (10%): 3.0s , <10M
公開 測資點#4 (10%): 3.0s , <10M
公開 測資點#5 (10%): 3.0s , <10M
公開 測資點#6 (10%): 3.0s , <10M
公開 測資點#7 (10%): 3.0s , <10M
公開 測資點#8 (10%): 3.0s , <10M
公開 測資點#9 (10%): 3.0s , <10M
提示 ：
$10\%：n,q\leq 2000$
$90\%：無特別限制$
標籤:
出處:
[管理者：
becaido
(Caido)
]
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
|
沒有發現任何「解題報告」
|
|||||