Yuno loves sqrt technology III
题意
区间询问众数，强制在线。
题解
经典分块题，记一下。
对于序列分块，记 \(f_{i,j}\) 代表第 \(i\) 个块到第 \(j\) 个块的众数出现次数。
考虑询问的时候怎么做，我们只需要考虑散块。
对于散块的元素 \(a_i\) 查找其在询问区间 \([l,r]\) 的个数，与 \(f_{i,j}\) 取 \(max\) 即可。
注意到直接嗯二分每次操作时间复杂度为 \(O(logn)\)，时间复杂度就会退化。
仍然考虑用分块解决，运用前缀和思想，用 \(g_{i,j}\) 表示值为 \(i\) 在前 \(j\) 个块中出现的次数。
这样问题就很 \(easy\) 了，时间复杂度 \(O(n\sqrt{n})\)，空间复杂度 \(O(n\sqrt{n})\)。
仔细一看发现空间爆了，只能修改做法了。
若当前的答案为 \(ans\)，则我们至少要出现次数为 \(ans+1\) 的数字来更新。
所以对于一个散块元素来说，我们只需要判断往一个方向第 \(ans+1\) 个相同的值的位置是否在 \([l,r]\) 即可。
容易发现 \(ans\) 的改变不会超过 \(2\sqrt{n}\)，所以时间复杂度不变，空间线性。
点击查看代码
#include <bits/stdc++.h>
#define rg register
#define pc putchar
#define gc getchar
#define pf printf
#define space pc(' ')
#define enter pc('\n')
#define me(x,y) memset(x,y,sizeof(x))
#define pb push_back
#define FOR(i,k,t,p) for(rg int i(k) ; i <= t ; i += p)
#define ROF(i,k,t,p) for(rg int i(k) ; i >= t ; i -= p)
using namespace std ;
bool s_gnd ;
inline void read(){}
template<typename T,typename ...T_>
inline void read(T &x,T_&...p)
{
x = 0 ;rg int f(0) ; rg char c(gc()) ;
while(!isdigit(c)) f |= (c=='-'),c = gc() ;
while(isdigit(c)) x = (x<<1)+(x<<3)+(c^48),c = gc() ;
x = (f?-x:x) ;
read(p...);
}
int stk[30],tp ;
inline void print(){}
template<typename T,typename ...T_>
inline void print(T x,T_...p)
{
if(x < 0) pc('-'),x = -x ;
do stk[++tp] = x%10,x /= 10 ; while(x) ;
while(tp) pc(stk[tp--]^48) ; space ;
print(p...) ;
}
bool S_GND ;
const int N = 5e5+5 ;
const int B = 720 ;
int n,q,top,le,ri,las ;
int vis[N],mx[B][B] ;
int a[N],pos[N],in[N],bl[N],br[N] ;
vector<int>vec[N] ;
void Solve()
{
if(le > ri) swap(le,ri) ;
if(le > n || ri > n) return ;
int res = 0 ;
if(in[le] == in[ri])
{
FOR(i,le,ri,1) ++vis[a[i]],res = max(res,vis[a[i]]) ;
FOR(i,le,ri,1) vis[a[i]] = 0 ; print(las=res),enter ;return ;
}
int A = in[le]+(le!=bl[in[le]]) ;
int B = in[ri]-(ri!=br[in[ri]]) ;
res = mx[A][B] ; int now ; //print(A,B),enter ;
if(le != bl[in[le]])
{
FOR(i,le,br[in[le]],1)
{
now = pos[i] ;
while(now+res < vec[a[i]].size() && vec[a[i]][now+res] <= ri) ++res ;
}
}
if(ri != br[in[ri]])
{
FOR(i,bl[in[ri]],ri,1)
{
now = pos[i] ;
while(now-res >= 0 && vec[a[i]][now-res] >= le) ++res ;
}
}
print(las=res),enter ;
}
signed main()
{
//cerr<<(double)(&s_gnd-&S_GND)/1024.0/1024.0 ;
// freopen(".in","r",stdin) ;
// freopen(".out","w",stdout) ;
read(n,q),top = (n-1)/B+1 ;
FOR(i,1,n,1) read(a[i]),vec[a[i]].pb(i),pos[i] = vec[a[i]].size()-1 ;
FOR(i,1,top,1) bl[i] = (i-1)*B+1,br[i] = min(i*B,n) ;
FOR(i,1,top,1) FOR(j,bl[i],br[i],1) in[j] = i ;
FOR(i,1,top,1)
{
me(vis,0) ; int res = 0 ;
FOR(j,i,top,1)
{
FOR(k,bl[j],br[j],1) ++vis[a[k]],res = max(res,vis[a[k]]) ;
mx[i][j] = res ;
}
}
me(vis,0) ;
while(q--) read(le,ri),le ^= las,ri ^= las,Solve() ;
return 0 ;
}