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
2 0 0 2 1 1 1 0 1 2
測資資訊：
記憶體限制：
128
MB
提示 ：
樣例的部分解釋：
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
[管理者：
morris1028
(碼畜)
]
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
|
沒有發現任何「解題報告」
|
|||||