P5048 [Ynoi2019 模拟赛] Yuno loves sqrt technology III

题目-P5048 [Ynoi2019 模拟赛] Yuno loves sqrt technology III

问题分析

查询区间众数出现的次数, 尝试对区间进行分块

假设已经知道了区间内众数出现的次数s ss, 那么只需要判断散列块中是否有哪个数字还能成为众数

对于每个数字记录出现的位置v vv,v [ a [ i ] ] v[a[i]]v[a[i]]代表a [ i ] a[i]a[i]出现的一些位置,p o s [ i ] pos[i]pos[i]代表a [ i ] a[i]a[i]在v [ a [ i ] ] v[a[i]]v[a[i]]中的索引

假设区间内众数出现的次数是a n s ansans

• 枚举所有左侧散列块, 假设数值是w ww, 那么只需要检查是否存在v [ w ] [ p o s [ i ] + a n s ] ≤ r v[w][pos[i] + ans] \le rv[w][pos[i]+ans]≤r, 就可以更新a n s ansans, 也就是算上当前位置,w ww出现的次数是a n s + 1 ans + 1ans+1
• 枚举右侧散列块, 假设数值是w ww, 检查v [ w ] [ p o s [ i ] − a n s ] ≥ l v[w][pos[i] - ans] \ge lv[w][pos[i]−ans]≥l, 算上当前位置,w ww出现的次数是a n s + 1 ans + 1ans+1

算法步骤

• 初始化分块, 对数据进行离散化
• 暴力初始化f ff数组

代码实现

#include<bits/stdc++.h>usingnamespacestd;constintN=5e5+10,M=710;intn,m,a[N];vector<int>vec;intbsize,bcnt,st[M],ed[M],b[N];vector<int>v[N];intpos[N],f[M][M],tot[N];voidinit(){bsize=sqrt(n);bcnt=(n-1)/bsize+1;for(inti=1;i<=bcnt;++i){st[i]=(i-1)*bsize+1;ed[i]=min(n,i*bsize);}for(inti=1;i<=n;++i)b[i]=(i-1)/bsize+1;sort(vec.begin(),vec.end());vec.erase(unique(vec.begin(),vec.end()),vec.end());}intfind(intx){returnlower_bound(vec.begin(),vec.end(),x)-vec.begin();}intquery(intl,intr){intx=b[l],y=b[r];if(x==y){intans=0;for(inti=l;i<=r;++i)tot[a[i]]=0;for(inti=l;i<=r;++i)ans=max(ans,++tot[a[i]]);returnans;}intans=f[x+1][y-1];for(inti=l;i<=ed[x];++i){intt=pos[i];if(i+t<v[a[i]].size()&&v[a[i]][i+t]<=r)ans++;}for(inti=st[y];i<=r;++i){intt=pos[i];if(t-ans>=0&&v[a[i]][t-ans]>=l)ans++;}returnans;}intmain(){ios::sync_with_stdio(false);cin.tie(0);cin>>n>>m;for(inti=1;i<=n;++i)cin>>a[i],vec.push_back(a[i]);init();for(inti=1;i<=n;++i)a[i]=find(a[i]);for(inti=1;i<=n;++i){v[a[i]].push_back(i);pos[i]=v[a[i]].size();pos[i]--;}for(inti=1;i<=bcnt;++i){memset(tot,0,sizeoftot);for(intj=i;j<=bcnt;++j){f[i][j]=f[i][j-1];for(intk=st[j];k<=ed[j];++k){f[i][j]=max(f[i][j],++tot[a[k]]);}}}intlast=0;while(m--){intl,r;cin>>l>>r;l^=last,r^=last;if(r<l)swap(l,r);intans=query(l,r);cout<<ans<<'\n';last=ans;}return0;}