給您一個 $(1, 2, ...,N)$ 的排列 $({P_1},{P_2},...,{P_N})$ 以及一個非負整數 $K$，對於所有 $(L,R)$ 符合 ${1 ≤ L ≤ R ≤ N}$，考慮以下條件:
- $max(P_L,P_{L+1}, ..., P_R) - min(P_L,P_{L+1},..., P_R) ≤ R - L + K$
我們稱符合上面條件的 $(P_L, ..., P_R)$ 為美麗的，請問存在幾組 $(L,R)$ 使得該區間是美麗的?
輸入第一行有個數字 $T$ 代表測資筆數。
每筆測資有兩行，第一行有一個數字 $N$ 代表該測資的排列 $P$ 長度，以及一個非負整數 $K$，接著一行有 $N$ 個數字代表排列 $P$ 的內容。
針對每筆測資，請輸出滿足所有條件的 $(L,R)$ 的總數量，注意答案可能超出 $2 \times 10^9$。
4 4 1 1 4 2 3 10 3 3 7 10 1 9 5 4 8 6 2 5 10000 1 5 2 4 3 2 0 2 1
9 37 15 3
公開 測資點#0 (10%): 2.0s , <1M
公開 測資點#1 (10%): 2.0s , <1M
公開 測資點#2 (10%): 2.0s , <1M
公開 測資點#3 (10%): 2.0s , <1M
公開 測資點#4 (10%): 2.0s , <1M
公開 測資點#5 (10%): 2.0s , <1M
公開 測資點#6 (10%): 2.0s , <1M
公開 測資點#7 (10%): 2.0s , <1M
公開 測資點#8 (10%): 2.0s , <1M
公開 測資點#9 (10%): 2.0s , <1M
針對第一個測資，$P=(1,4,2,3),\ K=1$，有 $(L,R) = (1,1)$、$(1,3)$、$(1,4)$、$(2,2)$、$(2,3)$、$(2,4)$、$(3,3)$、$(3,4)$、$(4,4)$，這 $9$ 組都符合條件，我們舉一個例子:
$(L,R)=(1,2)$ 時，$max(P_1,P_2)-min(P_1,P_2)=4-1=3$，$R-L+K=2$，不符合美麗的定義。
$(L,R)=(1,3)$ 時，$max(P_1,P_2,P_3)-min(P_1,P_2,P_3)=4-1=3$，$R-L+K=3$，是美麗的。
題目改編自：https://atcoder.jp/contests/abc248/tasks/abc248_h
對於所有測資滿足:
$1 ≤ T, N, K ≤ 10^5$
$1 ≤ \sum N ≤ 10^5$ (也就是一筆測資總共的 $N$ 不超過 $10^5$)
$P$ 是數字 $1 \sim N$ 的一種排列
子題配分
$30\%$ : $K=0$，其實和這題差不多。
$30\%$ : $K≤3$，和 AtCoder 原題一樣。
$40\%$ : 無其他限制
註：題目不是我出的，我只是幫忙放上來，若有任何問題，請洽出這題的人。
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
|
沒有發現任何「解題報告」
|
|||||