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

內容

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

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

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

輸入說明

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

第二行包括 $n$ 個整數 $s_1, s_2, ..., s_n$ ($1 \le s_i \le n$)。

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

輸出說明

對每個詢問，單獨輸出一行，表示 $[s_l, \text{... },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 (碼畜) ]

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