ZeroJudge b417 - 區間眾數 解題心得( 題目 )
解題概念:莫隊算法(Mo's algorithm)
解題方法:這題很難單獨使用一種資料結構(像Segment Tree)達到快速查詢，但是直接暴力複雜度O(mn)又太慢，我們考慮離線解法，首先假設使左界排序使得左界總共只O(n)，複雜度也是爆，因為最糟情況右界要移動mn次，如果我們使用莫隊，把區塊分成m^0.5個(也就是把查詢數m開根號)，先照每筆查詢左界所屬區塊排序，一樣就照右界排序，複雜度可以壓掉根號m，而至於為何是根號m，原因是因為根據算幾不等式在根號m複雜度最佳。
再來是確定眾數的辦法，維護num[x]代表數字x出現次數，並且維護tim[x]代表有這樣數量的數字出現x次，紀錄目前出現最多mux次，則tim[x]則是他求的種類數量，根據這個方法，即可以用O(1)移動指針。
我們利用移動左右指針來求每個查詢的結果，最後，總複雜度為O(n*m^0.5)。
註:下面使用一個網路上別人分享的技巧，就是右界排序從小到大、從大到小交錯，也許可以減少右界指針移動(?)
Java參考程式碼 (有更好意見可留言於下方，謝謝!)
//Author:En Chi Tsung(欉恩祁)
//Date:2021/12/30
import java.io.*;
import java.util.*;
public class zjb417 {
public static int ret,r,k,mux=0;
public static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
public static BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
public static int[] in=new int[100005];
public static int[] num=new int[100005];
public static int[] tim=new int[100005];
public static int[] ans1=new int[1000005];
public static int[] ans2=new int[1000005];
public static Q[] q;
public static double area;
public static void main(String[] args) throws Exception{
final int n=rint();
final int m=rint();
k=(int)Math.ceil(Math.pow(m,0.5));
area=(double)(m+1)/k;
q=new Q[m];
for(int i=1;i<=n;i++) in[i]=rint();
for(int i=0;i<m;i++)q[i]=new Q(i,rint(),rint());
Sort();
Mo();
for(int i=0;i<m;i++)bw.write(ans1[i]+" "+ans2[i]+"\n");
bw.flush();
}
public static void Sort() {
Arrays.parallelSort(q,new Comparator<Q>() {
public int compare(Q f,Q s) {
if(f.b==s.b) {
if(f.b%2==0) {
return f.r-s.r;
}
else {
return s.r-f.r;
}
}
else {
return f.b-s.b;
}
}
});
}
public static void Mo() {
final int m=q.length;
int l=1,r=0;
for(int i=0;i<m;i++) {
while(l>q[i].l)add(in[--l]);
while(r<q[i].r)add(in[++r]);
while(l<q[i].l)sub(in[l++]);
while(r>q[i].r)sub(in[r--]);
ans1[q[i].o]=mux;
ans2[q[i].o]=tim[mux];
}
return;
}
public static void sub(int x) {
tim[num[x]]--;
tim[--num[x]]++;
if(tim[mux]==0)mux--;
}
public static void add(int x) {
tim[num[x]]--;
tim[++num[x]]++;
if(tim[mux+1]>0)mux++;
}
public static int rint() throws Exception {
ret=0;//fast input
r=br.read();
while(r>47&&r<58) {
ret*=10;
ret+=(r&15);
r=br.read();
}
return ret;
}
}
class Q{
int o,l,r,b;
Q(int a,int x,int y){
o=a;
l=x;
r=y;
b=(int)((double)l/zjb417.area);
}
}
文章標籤
全站熱搜
