1. 首頁 > 生活百科 > >

洛谷P4168 蒲公英 分塊處理區間眾數模板

生活百科

題面 。
許久以前我還不怎么去機房的時候 ， 一位大佬好像一直在做這道題，他稱這道題目為“大分塊” 。
其實這道題目的思想不只可以用于處理區間眾數，還可以處理很多區間數值相關問題 。
讓我們在線處理區間眾數 。
數據范圍1e5，考慮分塊 。
先對蒲公英種類離散化 。

預處理
預處理出兩個數組 。
【洛谷P4168 蒲公英 分塊處理區間眾數模板】一個數組sum[ i ][ j ]表示第j種顏色到第i個分塊的前綴和 。
另一個數組 zhongshu[ i ][ j ]表示第i個分塊到第j個分塊這個區間內的眾數 。
維護這兩個操作時間復雜度都不能超過n3/2 。
第一個數組很好維護，輸入的時候將輸入位置對應分塊的相應種類加一，然后跑一遍前綴和即可 ， 時間復雜度n*n1/2 。
維護第二個數組 ， 我們需要先枚舉起始分塊 。
從起始分塊開始，枚舉終點分塊 ， 每枚舉一個終點分塊，更新這個分塊內元素對于區間眾數的貢獻 。
建立一個數組tmp[ i ]作為輔助數組表示顏色i出現次數 。
for(int i=1;i<=get_pos(n);i++){//枚舉起始分塊        int mx=0;//從當前這個起始分塊開始，到終點分塊位置的眾數for(int j=i;j<=get_pos(n);j++)//枚舉終點分塊            for(int k=(j-1)*len+1;k<=min(j*len,n);k++){                tmp[a[k]]++;//當前元素出現次數加一                if(tmp[a[k]]>tmp[mx])//若當前元素出現次數大于當前處理區間眾數的出現次數，則將眾數修改為當前元素                    mx=a[k];                if(!(tmp[a[k]]^tmp[mx]))//若當前元素與當前處理區間眾數出現次數相等，則取編號小的為眾數                    mx=min(mx,a[k]);            }            b_mos[i][j]=mx;//從分塊i到分塊j的眾數就是mx        }        for(int j=0;j<=ntot;j++)//清空輔助數組            tmp[j]=0;    }時間復雜度為n1/2 *（n+n1/2*n1/2），即n3/2 。
處理詢問
對于詢問的l，r，算出其所處分塊lb,rb 。
若l與r在同一分塊或在相鄰塊內，可以暴力求出眾數 ， 時間復雜度n1/2 。
int get_vio(){//vio指violent    int mx=0;    for(int i=l;i<=r;i++){        tmp[a[i]]++;        if(tmp[a[i]]>tmp[mx])//按比較規則進行更新 。            mx=a[i];        if(!(tmp[a[i]]^tmp[mx]))            mx=min(mx,a[i]);    }    for(int i=l;i<=r;i++)        tmp[a[i]]--;    return mx;}若l與r所在分塊中間相隔了至少一個分塊，那么所詢問區間的眾數只有兩種可能 。
  1. 中間那一段分塊的眾數
  2. 左端點所在塊與右端點所在塊內的數
不難理解 。
對于中間那一段分塊內的數，如果它們的出現次數要超過中間那一段分塊內的眾數，那么它們必須要在左端點所在塊和右端點所在塊內出現 。
先將中間那一段分塊的眾數設為答案 ， 再對左端點和右端點所在塊內的數統計出現次數并更新答案即可 。
int get_tim(int x){    return tmp[x]+b_sum[rb-1][x]-b_sum[lb][x];//計算某數的總出現次數}int get_q(){    int mx=b_mos[lb+1][rb-1];//先將答案設為中間那一段分塊內的眾數    for(int i=l;i<=lb*len;i++){        tmp[a[i]]++;        if(get_tim(a[i])>get_tim(mx))//按照比較規則更新答案            mx=a[i];        if(get_tim(a[i])==get_tim(mx))            mx=min(mx,a[i]);    }    for(int i=(rb-1)*len+1;i<=r;i++){        tmp[a[i]]++;        if(get_tim(a[i])>get_tim(mx))            mx=a[i];        if(get_tim(a[i])==get_tim(mx))            mx=min(mx,a[i]);    }    for(int i=l;i<=lb*len;i++)//清空輔助數組        tmp[a[i]]--;    for(int i=(rb-1)*len+1;i<=r;i++)        tmp[a[i]]--;    return mx;}

推薦閱讀