背景
在 2015 年 6 月的 Facebook 上，不少以「靠北」為前綴命名的粉絲頁面，就如 靠北工程師 為例，不少業界工程師匿名在上面抱怨工作過時、主管、生活 ... 等。突然有一篇 #靠北工程師7257 抱怨著編程競賽的零零種種，從回應中能明白存在業界工程師不清楚編程競賽，以 UI 介面、cmd 指令 ... 等方式理解比賽的目標、運行。
網路處處有答案，演算法和資料結構到底重不重要？抄下來能用就行，大部分的要求是不講求效率的，但對於曾經在編程競賽待過一陣子的小夥伴而言，看到他們的理解方式開始感到憤憤不平，進行了一陣子的爭吵。
過一陣子，大批的學生開始進入 靠北工程師 裡發文，開始爭論學校、系所哪個是比較有未來的，突然間有一位資管系的同學發問這一道算法題 #靠北工程師7780 ，結果一不小心就看錯題目，把種類數誤看成個數，於是討論了不少其他的算法來完成，現在就把這個問題交給你。
用各種算法解決這個誤解的題目。
問題描述
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$)，意義見題目描述。
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
3 0 0 2 1 3 1 0 1 2
公開 測資點#0 (20%): 1.0s , <1M
公開 測資點#1 (20%): 3.0s , <10M
公開 測資點#2 (20%): 6.0s , <10M
公開 測資點#3 (20%): 6.0s , <10M
公開 測資點#4 (20%): 6.0s , <50M
5 9 1 2
子序列為 4 1 5 1 2
在 [1,2] 裡的權值有 1,1,2，因此答案為 3。
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。
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
|
沒有發現任何「解題報告」
|
|||||