b417: 區間眾數
標籤 : 塊狀算法 眾數 莫隊算法
通過比率 : 89% (41 人 / 46 人 ) (非即時)
評分方式:
Tolerant

最近更新 : 2015-07-01 18:01

內容 :

背景

大學上課是怎麼回事的呢?談論到學期成績計算,很多奇聞軼事可以說的,例如教授任選三題批改同學任選三題作答滿分三百沒有考試、 ... 等。筆試類型的考試只是最常見的一種,還有所謂的多才華加分,例如上台報告舉手發問參與展覽參加競賽、 ... 等。

不幸地,某 M 修了一堂怪課,教授每一堂課結束後總是會大聲宣揚「葛萊分多加 5 分」對於需要不斷複習演練的某 M 而言,這門課的即時評分方式讓其非常挫敗。神奇的是,有一次教授這麼問同學「給一序列,請計算眾數平均數中位數,答對加分。」某 M 剎那間傻住,大學的學期成績可以用這種問題獲得,當他在懷疑這個問題時,問題早已被同學回答走。

某 M 非常不甘心,計算眾數、平均數、中位數就能夠加分,要求只是 n = 10 的序列。既然加分有理,出題吧!

題目描述

平均數、中位數可以藉由區間總和、區間 K 小問題來完成,現在來解決眾數。

給定一個長度為 $n$ ( $1 \le n \le 100000$ ) 的正整數序列 $s$ ($1 \le s_i \le n$),對於 $m$ ( $1 \le m \le 1000000$) 次詢問 $l, r$,每次輸出 $[s_l, \text{... },s_r]$ 中,出現最多次的次數以及有多少種數字出現最多次。

輸入說明

每個測資點,測資只有一組。

第一行包括兩個整數 $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$ 行,每行​​包括 2 個整數 $l, r,$ ($1 \le l \le r \le n$)。

輸出說明
對每個詢問,單獨輸出一行,表示 $[s_l, \text{... },s_r]$ 中,出現最多次的次數以及有多少種數字出現最多次。
範例輸入
10 10
2 3 1 1 1 2 1 2 1 1
5 8
1 10
6 9
5 9
1 5
3 10
1 9
1 1
6 9
2 3
範例輸出
2 2
6 1
2 2
3 1
3 1
6 1
5 1
1 1
2 2
1 2
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (20%): 1.0s , <1M
公開 測資點#1 (20%): 1.0s , <1M
公開 測資點#2 (20%): 1.0s , <10M
公開 測資點#3 (20%): 10.0s , <10M
公開 測資點#4 (20%): 10.0s , <10M
提示 :

5 8
子序列為 1 2 1 2
1 出現 2 次、2 出現 2 次,最多出現次數 2,有 2 種數字都出現 2 次。

1 10
子序列為 2 3 1 1 1 2 1 2 1 1
1 出現 6 次,其餘數字出現少於 6 次,最多出現次數 6,有 1 種數字出現 6 次。

6 9
子序列為 2 1 2 1
1 出現 2 次、2 出現 2 次,最多出現次數 2,有 2 種數字都出現 2 次。

5 9
子序列為 1 2 1 2 1
1 出現 3 次、2 出現 2 次,最多出現次數 3,有 1 種數字都出現 3 次。

標籤:
塊狀算法 眾數 莫隊算法
出處:
[編輯:
morris1028 (碼畜)
]
編號 身分 題目 主題 人氣 發表日期
沒有發現任何「解題報告」