2724: [Violet 6]蒲公英
Time Limit: 40 Sec Memory Limit: 512 MB
Submit: 1633 Solved: 563
[Submit][Status][Discuss]
Description
Input
修正一下
l = (l_0 + x - 1) mod n + 1, r = (r_0 + x - 1) mod n + 1
Output
Sample Input
6 3
1 2 3 2 1 2
1 5
3 6
1 5
1 2 3 2 1 2
1 5
3 6
1 5
Sample Output
1
2
1
2
1
HINT
修正下:
n <= 40000, m <= 50000
Source
分析:
第一次写分块的题目...所以无耻的copyhzwer...
感觉数据范围不大,可以用分块暴力...
对于两个整块ab,他们的众数一定存在于mode(a)∪b...脑补一下...
所以对于一个区间[l,r]的众数一定存在于中间整块的众数和两边不整块的所有数字...
这样我们如果可以快速查询区间[l,r]的x出现次数就能够解决问题...可以对于每个权值维护一个vector存下来它出现的位置(从大到小),然后二分查询就好了...
这样预处理的复杂度是n√n的,查询的复杂度是n√nlgn的...
代码:
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<map>
//by NeighThorn
using namespace std; const int maxn=+,blo=; map<int,int> mp; vector<int> v[maxn]; int n,m,cnt,ans,a[maxn],id[maxn],tot[maxn],val[maxn],f[+][+]; inline void init(int x){
int mode=,maxcnt=;
memset(tot,,sizeof(tot));
for(int i=(x-)*blo+;i<=n;i++){
tot[a[i]]++;
if(tot[a[i]]>maxcnt||(tot[a[i]]==maxcnt&&val[a[i]]<val[mode]))
mode=a[i],maxcnt=tot[a[i]];
f[x][id[i]]=mode;
}
} inline int qrycnt(int l,int r,int x){
return upper_bound(v[x].begin(),v[x].end(),r)-lower_bound(v[x].begin(),v[x].end(),l);
} inline int query(int l,int r){
int mode=f[id[l]+][id[r]-],maxcnt=qrycnt(l,r,mode);
for(int i=l;i<=min(r,id[l]*blo);i++){
int tmp=qrycnt(l,r,a[i]);
if(tmp>maxcnt||(tmp==maxcnt&&val[a[i]]<val[mode]))
mode=a[i],maxcnt=tmp;
}
if(id[l]!=id[r]){
for(int i=(id[r]-)*blo+;i<=r;i++){
int tmp=qrycnt(l,r,a[i]);
if(tmp>maxcnt||(tmp==maxcnt&&val[a[i]]<val[mode]))
mode=a[i],maxcnt=tmp;
}
}
return mode;
} signed main(void){
ans=cnt=;
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++){
scanf("%d",&a[i]);
if(mp.find(a[i])==mp.end())
mp[a[i]]=++cnt,val[cnt]=a[i];
a[i]=mp[a[i]];v[a[i]].push_back(i);
}
for(int i=;i<=n;i++)
id[i]=(i-)/blo+;
for(int i=;i<=id[n];i++)
init(i);
for(int i=,x,y;i<=m;i++){
scanf("%d%d",&x,&y);
x=(x+ans-)%n+,y=(y+ans-)%n+;
if(x>y)
swap(x,y);
ans=val[query(x,y)];
printf("%d\n",ans);
}
return ;
}
by NeighThorn