本文主要是介绍蒲公英 洛谷 - 4168，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
https://www.luogu.org/problem/show?pid=4168
块状数组求区间众数http://www.docin.com/p-679227660.html
这道题无修改 带修改的之后补上（之后没找到）
#include <bits/stdc++.h>
using namespace std;
const int sz=200;vector <int> pre[40010];
int big[210][210];
int ary[40010],tmp[40010],mp[40010],belong[40010],book[40010];
int n,q,len;void init(int x)
{int i,maxx,val;memset(book,0,sizeof(book));maxx=0,val=0;for(i=(x-1)*sz+1;i<=n;i++){book[mp[i]]++;if(maxx<book[mp[i]]||(maxx==book[mp[i]]&&val>mp[i])) maxx=book[mp[i]],val=mp[i];big[x][belong[i]]=val;}
}int getnum(int pl,int pr,int val)
{vector<int>::iterator y=upper_bound(pre[val].begin(),pre[val].end(),pr);vector<int>::iterator x=lower_bound(pre[val].begin(),pre[val].end(),pl);return y-x;
}int query(int pl,int pr)
{int i,maxx,val,res;val=big[belong[pl]+1][belong[pr]-1];maxx=getnum(pl,pr,val);for(i=pl;i<=pr&&belong[i]==belong[pl];i++){res=getnum(pl,pr,mp[i]);if(maxx<res||(maxx==res&&val>mp[i])) maxx=res,val=mp[i];}for(i=pr;i>=pl&&belong[i]!=belong[pl]&&belong[i]==belong[pr];i--){res=getnum(pl,pr,mp[i]);if(maxx<res||(maxx==res&&val>mp[i])) maxx=res,val=mp[i];}return val;
}int main()
{int i,l,r,ans;scanf("%d%d",&n,&q);for(i=1;i<=n;i++){scanf("%d",&ary[i]);tmp[i]=ary[i];}sort(tmp+1,tmp+n+1);len=unique(tmp+1,tmp+n+1)-tmp-1;for(i=1;i<=n;i++){mp[i]=lower_bound(tmp+1,tmp+len+1,ary[i])-tmp;pre[mp[i]].push_back(i);belong[i]=(i-1)/sz+1;}for(i=1;i<=belong[n];i++) init(i);ans=0;while(q--){scanf("%d%d",&l,&r);l=(l+ans-1)%n+1,r=(r+ans-1)%n+1;if(l>r) swap(l,r);ans=tmp[query(l,r)];printf("%d\n",ans);}return 0;
}
这篇关于蒲公英 洛谷 - 4168的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
