P4168 [Violet] 蒲公英 (离散化+分块 在线查询区间众数)
<h1 id="p4168-violet-蒲公英">P4168 蒲公英</h1><h3 id="离散化分块-在线查询区间众数">离散化+分块 在线查询区间众数</h3>
<p>由于a_i范围是1e9的,记录a_i出现的次数不方便直接用数组记录，但是一共有n个数，我们就可以把它们排序去重，把a_i映射为在n个数中排第几，这样映射后的值域就小于n了，我们就能直接用数组记录了，这就是离散化<br>
将长度为 n 的数组分块，每块长度为 B=sqrt(n)<br>
比如[0,B),[B,2*b)...[k*B,n)<br>
对于所查询的区间 设l位于块bl, r位于块br,<br>
|-------------------p1----------------p2---------------------|<br>
|------l-------------|-------------------|-----------r----------|</p>
<p>其中p1 = (bl+1)*B,p2 = br*B-1</p>
<p>该区间的众数只可能为在 $$内出现的数 和 块 $$的众数之间</p>
<blockquote>
<p>因为在加内出现的数的时候才会改变 块 的众数</p>
</blockquote>
<p>当bl和br位于同一个块或相邻块为了方便些代码就直接暴力复杂度最大$2*sqrt(n)$</p>
<p>否则就是在cnt数组中只维护内出现的数 和 块 的众数,这些数字最多也是sqrt(n)级别的，在遍历l->p_1和p_2->r用vis数组判断是否已经加了某个数在中的出现次数</p>
<p>p1->p2所有数出现的次数用前缀和维护<br>
这样总复杂度就是O(nlog(n)+(n+q)*sqrt(n))<br>
ac代码如下:</p>
<pre><code class="language-c++">#include<bits/stdc++.h>
using namespace std;
#define ull signed long long
// #define int long long
#define CINT \
// cin>>T;
void solve(){
int n,q;cin>>n>>q;
vector<int> a(n);
for(int i = 0;i<n;i++){
cin>>a;
}
vector<int> b = a;
// 离散化
sort(b.begin(),b.end());
b.erase(unique(b.begin(),b.end()),b.end());
for(int i = 0;i<n;i++){
a = lower_bound(b.begin(),b.end(),a)-b.begin();
}
int B = sqrt(n);
// 前缀和,存前i块各个数字出现的次数
vector<vector<int>> pre((n-1)/B+1,vector<int> (b.size()));
for(int i = 0;i<n;i+=B){
if(i!=0) pre = pre;
for(int j = i;j<min(n,i+B);j++){
pre]++;
}
}
// f表示第i块到第j块的众数
vector<vector<int>> f((n-1)/B+1,vector<int> ((n-1)/B+1));
vector<int> cnt(b.size()),vis(b.size());
for(int i = 0;i<=(n-1)/B;i++){
int p = 0,mx = 0;
fill(cnt.begin(),cnt.end(),0);
for(int j = i;j<=(n-1)/B;j++){
for(int k = j*B;k<min(n,j*B+B);k++){
cnt]++;
if(cnt]>mx || (cnt]==mx and a<p)){
p = a;
mx = cnt];
}
}
f = p;
}
}
fill(cnt.begin(),cnt.end(),0);
auto upd = [&](int num,int& p,int& mx,int bl,int br){
if(!vis){ //判断指定在中间区间的出现次数是否已经被加过
vis = 1;
cnt += pre-pre;
}
if(cnt>mx || (cnt==mx and num<p)){
p = num;
mx = cnt;
}
};
int x = 0;
while(q--){
int l,r;cin>>l>>r;
l = (l+x-1)%n+1;r = (r+x-1)%n+1;
l--,r--;
if(l>r) swap(l,r);
int bl = l/B,br = r/B;
int p = 0,mx = 0;
if(br-bl<=1){ //区间长度小于2*sqrt(n)直接暴力
for(int i = l;i<=r;i++){
cnt]++;
if(cnt]>mx || (cnt]==mx and a<p)){
p = a;
mx = cnt];
}
}
for(int i = l;i<=r;i++){
cnt] = 0;
}
}else{
for(int i = l;i<(bl+1)*B;i++){
cnt]++;
upd(a,p,mx,bl,br);
}
for(int i = br*B;i<=r;i++){
cnt]++;
upd(a,p,mx,bl,br);
}
upd(f,p,mx,bl,br);
// 还原操作
for(int i = l;i<(bl+1)*B;i++) cnt] = vis] = 0;
for(int i = br*B;i<=r;i++) cnt] = vis] = 0;
cnt] = vis] = 0;
}
x = b;
cout<<b<<"\n";
}
}
signed main(){
std::cin.tie(nullptr)->sync_with_stdio(false);
int T = 1;
CINT;
while(T--) solve();
return 0;
}
</code></pre><br><br>
来源：https://www.cnblogs.com/hyhgfrgh/p/19687542
頁:
[1]