在线版区间众数 hzw的代码。。

/* 查询区间众数，要求强制在线 设有T个块 1.众数只可能在大块[L,R]里或者两端[l,L) (R,r]里出现 2.大块的众数只要预处理打表一下即可，复杂度n*T(这样的区间有T*T个) 3.两端的众数需要枚举每个元素，然后查询这个元素在区间[l,r]里出现的次数 用一个vector记录每个值出现的位置，然后用二分找其在区间[l,r]出现的次数即可 这部分每次查询的复杂度是N/T*logN， 块长取sqrt(nlogn) */ #include<bits/stdc++.h> using namespace std; #define maxn 100005 int id,n,len,pos[maxn],v[maxn],val[maxn],f[500][500]; vector<int>ve[maxn]; map<int,int>mp;//哈希表 int cnt[maxn]; void pre(int p){//处理第p块到n整块区间众数 memset(cnt,0,sizeof cnt); int mx=0,ans=0; for(int i=(p-1)*len+1;i<=n;i++){ cnt[v[i]]++; int t=pos[i]; if(cnt[v[i]]>mx || cnt[v[i]]==mx && val[v[i]]<val[ans]) ans=v[i],mx=cnt[v[i]]; f[p][t]=ans; } } int query(int l,int r,int x){//查询[l,r]区间x出现了几次 int t=upper_bound(ve[x].begin(),ve[x].end(),r)-lower_bound(ve[x].begin(),ve[x].end(),l); return t; } int query(int a,int b){ int ans,mx,p=pos[a],q=pos[b]; ans=f[p+1][q-1]; mx=query(a,b,ans); for(int i=a;i<=min(p*len,b);i++){ int t=query(a,i,v[i]); if(t>mx || t==mx&&val[v[i]]<val[ans]) ans=v[i],mx=t; } if(p!=q) for(int i=(q-1)*len+1;i<=b;i++){ int t=query(i,b,v[i]); if(t>mx || t==mx&&val[v[i]]<val[ans]) ans=v[i],mx=t; } return ans; } int main(){ cin>>n;len=200; for(int i=1;i<=n;i++){ cin>>v[i]; if(mp[v[i]]==0){ mp[v[i]]=++id; val[id]=v[i]; } v[i]=mp[v[i]]; ve[v[i]].push_back(i); } for(int i=1;i<=n;i++) pos[i]=(i-1)/len+1; for(int i=1;i<=pos[n];i++) pre(i);//预处理 for(int i=1;i<=n;i++){ int a,b; cin>>a>>b; if(a>b)swap(a,b); cout<<val[query(a,b)]<<endl; } }

 

转载于:https://www.cnblogs.com/zsben991126/p/10586602.html