b414. BZOJ 3809 Gty 的二逼妹子序列 - 高中生程式解題系統

內容

Autumn 和 Bakser 又在研究 Gty 的妹子序列了！

但他們遇到了一個難題，對於一段妹子們，他們想讓你幫忙求出這之內美麗度 $s_{i} \in [a, b]$ 的妹子的美麗度的種類數。為了方便，我們規定妹子們的美麗度全都在 $[1, n]$ 中。

給定一個長度為 $n$ ( $1 \leq n \leq 100000$ ) 的正整數序列 $s$ ( $1 \leq s_{i} \leq n$ )，對於 $m$ ( $1 \leq m \leq 1000000$ ) 次詢問 $l, r, a, b$ ，每次輸出 $[s_{l}, ..., s_{r}]$ 中，權值 $s_{i} \in [a, b]$ 的權值種類數。

輸入說明

第一行包括兩個整數 $n, m$ ( $1 \leq n \leq 100000, 1 \leq m \leq 1000000$ )，表示數列 $s$ 中的元素數和詢問數。

第二行包括 $n$ 個整數 $s_{1}, s_{2}, . . ., s_{n}$ ( $1 \leq s_{i} \leq n$ )。

接下來 $m$ 行，每行包括 4 個整數 $l, r, a, b$ ( $1 \leq l \leq r \leq n, 1 \leq a \leq b \leq n$ )，意義見題目描述。

輸出說明

對每個詢問，單獨輸出一行，表示

[s_{l}, ..., s_{r}]

中，權值

s_{i} \in [a, b]

的權值種類數。

範例輸入 #1

10 10
4 4 5 1 4 1 5 1 2 1
5 9 1 2
3 4 7 9
4 4 2 5
2 3 4 7
5 10 4 4
3 9 1 1
1 4 5 9
8 9 3 3
2 2 1 6
8 9 1 4

範例輸出 #1

測資資訊：

記憶體限制： 128 MB
公開測資點#0 (20%): 3.0s , <1M
公開測資點#1 (20%): 3.0s , <10M
公開測資點#2 (20%): 5.0s , <10M
公開測資點#3 (20%): 6.0s , <10M
公開測資點#4 (10%): 6.0s , <50M
公開測資點#5 (10%): 6.0s , <50M

提示：

樣例的部分解釋：

5 9 1 2
子序列為 4 1 5 1 2
在 [1,2] 裡的權值有 1,1,2，有 2 種，因此答案為 2。

3 4 7 9
子序列為 5 1
沒有權值在 [7,9] 中的，因此答案為 0。

4 4 2 5
子序列為 1
沒有權值在 [2,5] 中的，因此答案為 0。

2 3 4 7
子序列為 4 5
權值在 [4,7] 中的有 4,5，因此答案為 2。

標籤:

出處:

BZOJ 3809 [管理者： morris821028@gmail.com

morris1028 (碼畜) ]

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