i341. 美麗的子序列 - Extreme - 高中生程式解題系統

內容

給您一個 $(1, 2, . . ., N)$ 的排列 $(P_{1}, P_{2}, . . ., P_{N})$ 以及一個非負整數 $K$ ，對於所有 $(L, R)$ 符合 $1 \leq L \leq R \leq N$ ，考慮以下條件:

$m a x (P_{L}, P_{L + 1}, . . ., P_{R}) - m i n (P_{L}, P_{L + 1}, . . ., P_{R}) \leq R - L + K$

我們稱符合上面條件的 $(P_{L}, . . ., P_{R})$ 為美麗的，請問存在幾組 $(L, R)$ 使得該區間是美麗的?

輸入說明

輸入第一行有個數字 $T$ 代表測資筆數。

每筆測資有兩行，第一行有一個數字 $N$ 代表該測資的排列 $P$ 長度，以及一個非負整數 $K$ ，接著一行有 $N$ 個數字代表排列 $P$ 的內容。

輸出說明

針對每筆測資，請輸出滿足所有條件的 $(L, R)$ 的總數量，注意答案可能超出 $2 \times 10^{9}$ 。

範例輸入 #1

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

範例輸出 #1

測資資訊：

記憶體限制： 128 MB
公開測資點#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)$ 時， $m a x (P_{1}, P_{2}) - m i n (P_{1}, P_{2}) = 4 - 1 = 3$ ， $R - L + K = 2$ ，不符合美麗的定義。

$(L, R) = (1, 3)$ 時， $m a x (P_{1}, P_{2}, P_{3}) - m i n (P_{1}, P_{2}, P_{3}) = 4 - 1 = 3$ ， $R - L + K = 3$ ，是美麗的。

題目改編自：https://atcoder.jp/contests/abc248/tasks/abc248_h

對於所有測資滿足:

$1 \leq T, N, K \leq 10^{5}$

$1 \leq \sum N \leq 10^{5}$ (也就是一筆測資總共的 $N$ 不超過 $10^{5}$ )

$P$ 是數字 $1 \sim N$ 的一種排列

子題配分

$30 %$ : $K = 0$ ，其實和這題差不多。

$30 %$ : $K \leq 3$ ，和 AtCoder 原題一樣。

$40 %$ : 無其他限制

註：題目不是我出的，我只是幫忙放上來，若有任何問題，請洽出這題的人。

標籤:

BIT 分治資料結構

出處:

AtCoder Beginner Contest 248Ex [管理者： beckzerojudge@gmail.com

becaido (Caido) ]

編號	身分	題目	主題	人氣	發表日期
沒有發現任何「解題報告」