题面太美不忍不放
分块分块
这种题的一个特点是只有查询，通常需要预处理；加入修改的话需要暴力重构预处理
预处理$f[i][j]$为第i块到第j块的众数，显然$f[i][j]=max{f[i][j-1],j中出现的数}$，复杂度$O(N^2/S)$，常数比较小吧
最近用$pair$上瘾了...
然后查询$[l,r]$时，整块直接查，两边不完整的枚举出现的数，然后加上整块里出现次数来更新
求整块的出现次数，可以用$v[i]$表示数字$i$出现位置，二分来找，复杂度$O(NSlogN)$
或者clj orz的论文里还有预处理的方法，预处理$s[i][x]$前i个块x的次数和$ss[i][j][x]$第i块前j个中k出现次数，貌似代码量会很大....
所以说这种vector+二分来找一个区间内某个数出现次数还是比较巧妙的呀....
然后分块一定要分$\sqrt{\frac{N}{logN}}$大小，比根号快了1倍多.....
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;
#define pii pair<int, int>
#define MP make_pair
#define fir first
#define sec second
const int N=4e4+,M=;
typedef unsigned long long ll;
inline int read(){
char c=getchar();int x=,f=;
while(c<''||c>''){if(c=='-')f=-;c=getchar();}
while(c>=''&&c<=''){x=x*+c-'';c=getchar();}
return x*f;
}
int n,Q,x,y,a[N],mp[N];
vector<int> v[N];
int pos[N],m,block;
struct _blo{int l,r;} b[M];
inline void ini(){
if(n==) block=;
else block=sqrt(n/log2(n));
m=(n-)/block+;
for(int i=;i<=n;i++) pos[i]=(i-)/block+;
for(int i=;i<=m;i++) b[i].l=(i-)*block+,b[i].r=i*block;
b[m].r=n;
}
//struct I{int x; bool operator <(const I &r) const{return x>r.x;} I(int a=0):x(a){} };
pii f[M][M];
int c[N];
struct Block{
void set(int x){
memset(c,,sizeof(c));
pii now(,);
for(int i=b[x].l;i<=n;i++){
c[a[i]]++; int t=pos[i];
now=max(now,MP( c[a[i]],-a[i] ) );//-a[i]
f[x][t]=now;
}
}
int cou(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);
}
int que(int l,int r){//printf("que %d %d\n",l,r);
pii re=f[pos[l]+][pos[r]-];
if(pos[l]==pos[r])
for(int i=l;i<=r;i++) re=max(re,MP( cou(l,r,a[i]),-a[i] ) );
else{
for(int i=l;i<=b[pos[l]].r;i++) re=max(re,MP( cou(l,r,a[i]),-a[i] ) );
for(int i=b[pos[r]].l;i<=r;i++) re=max(re,MP( cou(l,r,a[i]),-a[i] ) );
}
return -re.sec;
}
}B;
int main(){
freopen("in","r",stdin);
n=read();Q=read();
for(int i=;i<=n;i++) a[i]=mp[i]=read();
sort(mp+,mp++n); mp[]=unique(mp+,mp++n)-mp-;
for(int i=;i<=n;i++)
a[i]=lower_bound(mp+,mp++mp[],a[i])-mp , v[a[i]].push_back(i);
ini();
for(int i=;i<=m;i++) B.set(i);
int last=;
while(Q--){
int l=(read()+last-)%n+,r=(read()+last-)%n+;
if(l>r) swap(l,r);
last=mp[ B.que(l,r) ];
printf("%d\n",last);
}
}
7796ms
[2017-03-15 16:41:05]
又想了一下，$ss$其实不用预处理，查询的时候暴力算就行了
然后来享受没有$log$的优越，3372ms到第一页啦啦啦
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
#define pii pair<int, int>
#define MP make_pair
#define fir first
#define sec second
const int N=4e4+,M=;
typedef unsigned long long ll;
inline int read(){
char c=getchar();int x=,f=;
while(c<''||c>''){if(c=='-')f=-;c=getchar();}
while(c>=''&&c<=''){x=x*+c-'';c=getchar();}
return x*f;
}
int n,Q,x,y,a[N],mp[N];
int pos[N],m,block;
struct _blo{int l,r;} b[M];
inline void ini(){
block=sqrt(n);
m=(n-)/block+;
for(int i=;i<=n;i++) pos[i]=(i-)/block+;
for(int i=;i<=m;i++) b[i].l=(i-)*block+,b[i].r=i*block;
b[m].r=n;
} pii f[M][M];
int c[N],s[M][N];
struct Block{
void set(int x){
memset(c,,sizeof(c));
pii now(,);
for(int i=b[x].l;i<=n;i++){
c[a[i]]++; int t=pos[i];
now=max(now,MP( c[a[i]],-a[i] ) );
f[x][t]=now;
}
for(int i=;i<=mp[];i++) s[x][i]=s[x-][i];
for(int i=b[x].l;i<=b[x].r;i++) s[x][a[i]]++;
} int t[N];
int que(int l,int r){
pii re=f[pos[l]+][pos[r]-];
if(pos[l]==pos[r]){
for(int i=l;i<=r;i++) t[a[i]]=;
for(int i=l;i<=r;i++) re=max(re,MP( ++t[a[i]],-a[i] ) );
}else{
int L=pos[l],R=pos[r]-;
for(int i=l;i<=b[pos[l]].r;i++) t[a[i]]=s[R][ a[i] ] - s[L][ a[i] ];
for(int i=b[pos[r]].l;i<=r;i++) t[a[i]]=s[R][ a[i] ] - s[L][ a[i] ];
for(int i=l;i<=b[pos[l]].r;i++) re=max(re,MP( ++t[a[i]],-a[i] ) );
for(int i=b[pos[r]].l;i<=r;i++) re=max(re,MP( ++t[a[i]],-a[i] ) );
}
return -re.sec;
}
}B;
int main(){
freopen("in","r",stdin);
n=read();Q=read();
for(int i=;i<=n;i++) a[i]=mp[i]=read();
sort(mp+,mp++n); mp[]=unique(mp+,mp++n)-mp-;
for(int i=;i<=n;i++)
a[i]=lower_bound(mp+,mp++mp[],a[i])-mp; ini();
for(int i=;i<=m;i++) B.set(i);
int last=;
while(Q--){
int l=(read()+last-)%n+,r=(read()+last-)%n+;
if(l>r) swap(l,r);
last=mp[ B.que(l,r) ];
printf("%d\n",last);
}
}