【AcWing 249. 蒲公英】

題意：

長度為n的序列，給定區間，求區間眾數，如果出現次數相同，輸出編號最小的

題解：

區間眾數，不帶修改，強制在線（否則可以莫隊）
沒有什么好辦法那就只能暴力分塊
分塊，預處理任意兩個大塊之間的眾數，相當于求出所有后綴的眾數情況（枚舉左塊的端點，n*sqrt(n)）
詢問[l,r]中眾數肯定是大塊idl+1 ~ idr-1的眾數，或者小塊中的某個數
這一共是有sqrt(n)個候選答案，需要統計其在區間[l,r]內的出現次數，
第一個方法是用adj[x]記錄x的所有出現次數，那么x在[l,r]內的出現次數就是：

upper_bound(adj[x].begin(), adj[x].end(), r) - lower_bound(adj[x].begin(), adj[x].end(), l)

這個做法的復雜度是O(nsqrt(n)logn)
第二個方法是預處理每個數在所有塊中出現次數的前綴（n*sqrt(n)），這樣直接就可以用差分來求次數，可以省掉第一個方法中的查找（去掉log），復雜度O(nsqrt(n))

代碼：

代碼有詳細注釋
貌似方法一會超時，只有方法二可以過

方法一:

#pragma optimize("Ofast") #include<bits/stdc++.h> #define MAXN 40005 #define MAXB 2005 using namespace std; typedef long long ll;int N,M,B; int a[MAXN], c[MAXN]; int d[MAXB][MAXB];vector<int> adj[MAXN];void init(){int cnt[MAXN], res;for(int l=0;l<=N;l+=B)//枚舉左塊 {if(l==0) continue;memset(cnt, 0, sizeof(cnt));res = 0;for(int r=l;r<=N;r++)//枚舉右邊界 {++cnt[a[r]];bool f1=cnt[a[r]] > cnt[res];//出現次數最多 bool f2=( cnt[a[r]] == cnt[res] && a[r] < res);//出現次數一樣，編號更小 if(f1||f2) res = a[r];if((r+1)%B==0 || r==N) d[l/B][r/B] = res;//第l/B塊到第r/B塊的眾數是res }} }inline int num(const int& l, const int& r, const int& x){//在[l,r]范圍內x出現幾次 return upper_bound(adj[x].begin(), adj[x].end(), r) - lower_bound(adj[x].begin(), adj[x].end(), l); }int query(int l, int r){int ans = 0;int idl = l/B, idr = r/B;if(idl-1 < idr) //如果idl在idr的左側（或者一樣） ans = d[idl+1][idr-1];int n = num(l,r,ans), n1;//n和n1表示出現數量//ans為出現次數最多的數的編號 //-----以下為分塊的常規操作 if(idl==idr){for(int i=l;i<=r;i++){n1 = num(l,r,a[i]);//查看塊內是否有數字大于n if(n < n1 || n == n1 && a[i] < ans) ans = a[i], n = n1;}}else{for(int i=l;i<(idl+1)*B;i++){n1 = num(l,r,a[i]);if(n < n1 || n == n1 && a[i] < ans) ans = a[i], n = n1;}for(int i=idr*B;i<=r;i++){n1 = num(l,r,a[i]);if(n < n1 || n == n1 && a[i] < ans) ans = a[i], n = n1;}}return c[ans]; }int main(){scanf("%d%d", &N, &M);B = sqrt(N); for(int i=1;i<=N;i++){scanf("%d", &a[i]);}memcpy(c,a,sizeof(a));sort(c+1, c+1+N);for(int i=1;i<=N;i++){a[i] = lower_bound(c+1, c+1+N, a[i]) - c;adj[a[i]].push_back(i);//a[i]在哪些位置出現過 }//init();int last = 0, l, r;while(M--){scanf("%d%d", &l, &r);l = (l+last-1)%N + 1;r = (r+last-1)%N + 1;if(l > r) swap(l, r);//cout<<"l r "<<l<<" "<<r<<endl;last = query(l,r);printf("%d\n", last);}return 0; }

方法二：

#pragma optimize("Ofast") #include<bits/stdc++.h> #define MAXN 40005 #define MAXB 2005 using namespace std; typedef long long ll;int N,M,B; int a[MAXN], c[MAXN]; int s[MAXB][MAXN], d[MAXB][MAXB];inline int num(int idl, int idr, int x){//利用差分求出現次數 if(idl>idr) return 0;if(idl==0) return s[idr][x];else return s[idr][x] - s[idl-1][x]; } int cnt[MAXN]; void init(){for(int i=0;i<N;i++){if(i>0 && i%B==0){//到了下一塊 for(int j=0;j<N;j++){s[i/B][j] = s[i/B-1][j];//賦值前一塊的情況 }}++s[i/B][a[i]];}// 上述內容為預處理每個數在所有塊中出現次數的前綴 //下方內容為求出任意2個大塊之間的眾數int res;for(int l=0;l<N;l+=B){memset(cnt, 0, sizeof(cnt));res = 0;for(int r=l;r<N;r++){++cnt[a[r]];if(cnt[a[r]] > cnt[res] || cnt[a[r]] == cnt[res] && a[r] < res) res = a[r];if((r+1)%B==0 || (r+1)==N) d[l/B][r/B] = res;}} }int query(int l, int r){int ans = 0;int idl = l/B + 1, idr = r/B - 1;if(idl <= idr) ans = d[idl][idr];int n = num(idl,idr,ans), n1;if(l/B == r/B){for(int i=l;i<=r;i++) ++cnt[a[i]];for(int i=l;i<=r;i++){if(cnt[a[i]]==0) continue;n1 = num(idl, idr, a[i]) + cnt[a[i]];if(n < n1 || n == n1 && a[i] < ans) ans = a[i], n = n1;cnt[a[i]] = 0;}}else{for(int i=l;i<idl*B;i++) ++cnt[a[i]];for(int i=(idr+1)*B;i<=r;i++) ++cnt[a[i]];for(int i=l;i<idl*B;i++){if(cnt[a[i]]==0) continue;n1 = num(idl, idr, a[i]) + cnt[a[i]];if(n < n1 || n == n1 && a[i] < ans) ans = a[i], n = n1;cnt[a[i]] = 0;}for(int i=(idr+1)*B;i<=r;i++){if(cnt[a[i]]==0) continue;n1 = num(idl, idr, a[i]) + cnt[a[i]];if(n < n1 || n == n1 && a[i] < ans) ans = a[i], n = n1;cnt[a[i]] = 0;}}return c[ans]; }int main(){//ios::sync_with_stdio(0);scanf("%d%d", &N, &M);B = sqrt(N); for(int i=0;i<N;i++){scanf("%d", &a[i]);}memcpy(c,a,sizeof(a));sort(c, c+N);for(int i=0;i<N;i++){a[i] = lower_bound(c, c+N, a[i]) - c;}//init();memset(cnt, 0, sizeof(cnt));int last = 0, l, r;while(M--){scanf("%d%d", &l, &r);l = (l+last-1)%N + 1;r = (r+last-1)%N + 1;if(l > r) swap(l, r);--l; --r;//cout<<"l r "<<l<<" "<<r<<endl;last = query(l,r);printf("%d\n", last);}return 0; }

總結

以上是生活随笔為你收集整理的【AcWing 249. 蒲公英】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。