b417. 區間眾數
Tags : 塊狀算法 眾數 莫隊算法
Accepted rate : 176人/195人 ( 90% ) [非即時]
評分方式:
Tolerant

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

Content

背景

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

不幸地,某 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]$ 中,出現最多次的次數以及有多少種數字出現最多次。

Input

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

第一行包括兩個整數 $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$)。

Output
對每個詢問,單獨輸出一行,表示 $[s_l, \text{... },s_r]$ 中,出現最多次的次數以及有多少種數字出現最多次。
Sample Input #1
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
Sample Output #1
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
Hint :

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 次。

Tags:
塊狀算法 眾數 莫隊算法
出處:
[管理者: morris1028 (碼畜) ]

Status Forum 排行

ID User Problem Subject Hit Post Date
28753 r1cky (hehe) b417
Java 解題心得
380 2021-12-30 20:20