題目鏈接
題目大意：給定\(n\)個(gè)數(shù)和\(m\)個(gè)求區(qū)間眾數(shù)的詢問，強(qiáng)制在線

這題我\(debug\)了整整一個(gè)下午啊。。-_- 從14：30~16：45終于\(debug\)出來了，\(debug\)的難度主要就在\(Luogu\)數(shù)據(jù)不能下載，然后\(Contest Hunter\)的數(shù)據(jù)又太大了（最小的\(n=500,m=1000\)），只能人工查錯(cuò)，一行行檢查代碼，哎。。。寫不出正解還是算了吧，考試時(shí)可沒有這么多時(shí)間\(debug\)。

做法：先離散化，然后分塊，每塊大小\(\sqrt n\)，預(yù)處理任意兩塊之間的眾數(shù)，每個(gè)編號(hào)前\(k\)塊出現(xiàn)的次數(shù)，也就是前綴和，我們就能很快求出任意兩塊之間\(k\)出現(xiàn)的次數(shù)了。
把要求的區(qū)間\([l,r]\)分成3個(gè)部分，左邊不足一塊的部分，右邊不足一塊的部分和中間的很多塊，那么眾數(shù)只可能出現(xiàn)在：
1，左邊、右邊不足一塊的部分
2，中間很多塊的眾數(shù)
也就是說，中間很多塊的不是眾數(shù)又沒在左右兩部分出現(xiàn)過的，都不可能是\([l,r]\)的眾數(shù)。
于是暴力掃一邊左右兩個(gè)部分，對(duì)于每個(gè)數(shù)\(i\)，第一次掃到\(i\)的時(shí)候把計(jì)數(shù)器加上中間那些塊里面\(i\)的出現(xiàn)次數(shù)，不斷更新眾數(shù)。
最后判斷一下如果中間那些塊的眾數(shù)沒在左右部分出現(xiàn)過，那么再用中間那些塊的眾數(shù)嘗試更新答案。

Code:

（保留了debug）

#include <cstdio> #include <cmath> #include <algorithm> #include <cstring> #define re register const int MAXN = 40010; const int MAXSIZE = 800; using namespace std; inline int read(){int s = 0, w = 1;char ch = getchar();while(ch < '0' || ch > '9') { if(ch == '-') w = -1; ch = getchar(); }while(ch >= '0' && ch <= '9') { s = s * 10 + ch - '0'; ch = getchar(); }return s * w; } struct point{int id, val;point(){ id = val = 0; }bool operator < (const point A) const{return val < A.val;} }s[MAXN]; int SIZE; int common[MAXSIZE][MAXSIZE], belong[MAXN], a, b, pos[MAXN], p[MAXN][MAXSIZE], c[MAXN], d[MAXN], cnt, num, ans; int n, m; inline int get(int l, int r, int k){return p[k][r] - p[k][l - 1]; } int Solve(int l, int r){if(l > r) swap(l, r);int Com = 0, Max = 0;if(belong[l] == belong[r]){for(int i = l; i <= r; ++i)if(++c[pos[i]] > Max || (c[pos[i]] == Max && pos[i] < Com)) Max = c[pos[i]], Com = pos[i];for(int i = l; i <= r; ++i)c[pos[i]] = 0;}else if(belong[r] - belong[l] == 1){int e = belong[l] * SIZE;for(int i = l; i <= e; ++i)if(++c[pos[i]] > Max || (c[pos[i]] == Max && pos[i] < Com)) Max = c[pos[i]], Com = pos[i];for(int i = (belong[r] - 1) * SIZE + 1; i <= r; ++i)if(++c[pos[i]] > Max || (c[pos[i]] == Max && pos[i] < Com)) Max = c[pos[i]], Com = pos[i];for(int i = l; i <= e; ++i) c[pos[i]] = 0;for(int i = (belong[r] - 1) * SIZE + 1; i <= r; ++i) c[pos[i]] = 0;}else{int e = belong[l] * SIZE;for(int i = l; i <= e; ++i){if(++c[pos[i]] == 1) c[pos[i]] += get(belong[l] + 1, belong[r] - 1, pos[i]);if(c[pos[i]] > Max || (c[pos[i]] == Max && pos[i] < Com)) Max = c[pos[i]], Com = pos[i];}for(int i = (belong[r] - 1) * SIZE + 1; i <= r; ++i){if(++c[pos[i]] == 1) c[pos[i]] += get(belong[l] + 1, belong[r] - 1, pos[i]);if(c[pos[i]] > Max || (c[pos[i]] == Max && pos[i] < Com)) Max = c[pos[i]], Com = pos[i];}int L = belong[l] + 1; int R = belong[r] - 1;if(!c[common[L][R]]){c[common[L][R]] += get(L, R, common[L][R]);if(c[common[L][R]] > Max || (c[common[L][R]] == Max && common[L][R] < Com)) Com = common[L][R];c[common[L][R]] = 0;}for(int i = l; i <= e; ++i) c[pos[i]] = 0;for(int i = (belong[r] - 1) * SIZE + 1; i <= r; ++i) c[pos[i]] = 0;}return d[Com]; } int main(){//freopen("xsxs.txt","r",stdin);//freopen("xslb.txt","w",stdout);scanf("%d%d", &n, &m);SIZE = sqrt(n + 0.5); num = ceil((double)n / SIZE);for(int i = 1; i <= n; ++i){belong[i] = (i - 1) / SIZE + 1; //屬于哪塊s[i].id = i;scanf("%d", &s[i].val);}sort(s + 1, s + n + 1);for(int i = 1; i <= n; ++i){ //離散化if(s[i].val != s[i - 1].val)pos[s[i].id] = ++cnt;else pos[s[i].id] = cnt;d[cnt] = s[i].val;}for(int i = 1; i <= n; ++i)++p[pos[i]][belong[i]];for(int i = 1; i <= n; ++i)for(int j = 2; j <= num; ++j)p[i][j] += p[i][j - 1]; //前綴和for(int i = 1; i <= num; ++i){ //任意兩塊的眾數(shù)int Max = 0, cm = 0;for(int j = i; j <= num; ++j){for(int k = (j - 1) * SIZE + 1; k <= SIZE * j; ++k)if(++c[pos[k]] > Max || (c[pos[k]] == Max && pos[k] < cm)) //出現(xiàn)次數(shù)最多且編號(hào)最小的為眾數(shù)Max = c[pos[k]], cm = pos[k];common[i][j] = common[j][i] = cm;}memset(c, 0, sizeof c);}for(int i = 1; i <= m; ++i){scanf("%d%d", &a, &b);printf("%d\n", ans = Solve((a + ans - 1) % n + 1, (b + ans - 1) % n + 1));}/*int Max = 0;for(int i = 60; i <= 362; ++i){printf("%d ", d[pos[i]]);if(d[pos[i]] == 39881273) printf("\n%d\n", pos[i]);if(++c[pos[i]] > Max) Max = c[pos[i]];}*///printf("\n%d", d[41]);//fclose(stdin);//fclose(stdout);//system("pause");return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/Qihoo360/p/9555491.html

總結(jié)

以上是生活随笔為你收集整理的【洛谷 P4168】[Violet]蒲公英（分块）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。