強制線上區間衆數（分塊）

題意

給出一個長度為 n n n 的序列，有 m m m 次詢問，每次詢問給出 [ l , r ] [l,r] [l,r]，求區間衆數。強制線上。

n , m ≤ 500000 n,m\leq 500000 n,m≤500000。

分析

首先對 a i a_i ai​ 離散化，現在值域變成了 [ 1 , n ] [1,n] [1,n]。

考慮分塊。

首先，設 f i , j f_{i,j} fi,j​ 表示第 i i i 塊到第 j j j 塊之間的衆數，這個可以在 O ( n n ) O(n\sqrt{n}) O(nn

​) 求出。具體做法是對于每一個塊， O ( n ) O(n) O(n) 掃一遍求出衆數。

然後，詢問的時候，衆數隻可能有兩種情況：

• 衆數不是不完整塊中的數

  此時答案就是 f b l l + 1 , b l r − 1 f_{bl_{l}+1,bl_{r}-1} fbll​+1,blr​−1​。

• 衆數是不完整塊中的數

  首先設答案初值為 f b l l + 1 , b l r − 1 f_{bl_{l}+1,bl_{r}-1} fbll​+1,blr​−1​，出現次數為 m x mx mx。

  然後我們可以 O ( n ) O(\sqrt{n}) O(n

  ​) 暴力枚舉這個數，然後考慮這個數在 [ l , r ] [l,r] [l,r] 出現的次數是不是大于 m x mx mx。怎麼看一個數在 [ l , r ] [l,r] [l,r] 的出現次數呢？我們對每個數開一個 v e c t o r vector vector，存這個數所有出現的位置，然後 u p p e r _ b o u n d upper\_bound upper_bound 減 l o w e r _ b o u n d lower\_bound lower_bound 就行了。這樣複雜度是 O ( n n l o g n ) O(n\sqrt{n}logn) O(nn

  ​logn) 的。

  考慮優化，在枚舉左邊的數 a i a_i ai​ 時，我們可以存儲目前數在 v e c t o r vector vector 裡面出現的位置，記作 p o s i pos_i posi​，如果 p o s i + m x pos_i+mx posi​+mx 不超過 v e c t o r vector vector 的大小，而且 v a i , p o s i + m x ≤ r v_{a_i,pos_i+mx}\leq r vai​,posi​+mx​≤r，說明 a i a_i ai​ 在區間 [ l , r ] [l,r] [l,r] 出現了大于 m x mx mx 次，此時可以 m x = m x + 1 mx = mx + 1 mx=mx+1。

由于 m x mx mx 隻會更新不超過 2 n 2\sqrt{n} 2n

​ 次，是以總複雜度為 O ( n n ) O(n\sqrt{n}) O(nn

​)。

這裡給出 蒲公英 的代碼。

代碼如下：

#include <bits/stdc++.h>
#include <ext/pb_ds/hash_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;

LL z = 1;

int ksm(int a, int b, int p){
	int s = 1;
	while(b){
		if(b & 1) s = z * s * a % p;
		a = z * a * a % p;
		b >>= 1;
	}
	return s;
}

const int N = 5e5 + 5;
int a[N], b[N], pos[N], B, bl[N], cnt[N], L[710], R[710], f[710][710], tot, n;
vector<int> v[N];

void init(int x){
	int ans = 0, mx = 0;
	for(int i = L[x]; i <= n; i++){
		cnt[a[i]]++;
		if(cnt[a[i]] > mx || (cnt[a[i]] == mx && ans > a[i])) mx = cnt[a[i]], ans = a[i];
		f[x][bl[i]] = ans;
	}//f[i][j] 表示第 i 塊到第 j 塊的衆數 
	for(int i = L[x]; i <= n; i++) cnt[a[i]]--;
}

int QUERY(int l, int r){
	int ans = 0, mx = 0;
	for(int i = l; i <= r; i++){
		cnt[a[i]]++;
		if(cnt[a[i]] > mx || (cnt[a[i]] == mx && ans > a[i])) mx = cnt[a[i]], ans = a[i];
	}
	for(int i = l; i <= r; i++) cnt[a[i]]--;
	return ans;
}


int query(int l, int r){
	if(bl[l] == bl[r]) return QUERY(l, r);
	int ans = f[bl[l] + 1][bl[r] - 1], mx = upper_bound(v[ans].begin(), v[ans].end(), r) - lower_bound(v[ans].begin(), v[ans].end(), l);//中間的塊的衆數及出現次數 
	for(int i = l; i <= R[bl[l]]; i++){//左邊不完整塊 
		if(pos[i] + mx - 1 < v[a[i]].size() && v[a[i]][pos[i] + mx - 1] <= r){
			if(a[i] < ans) ans = a[i];
		}//如果 a[i] 出現次數大于等于 mx 次且 a[i] 更小，就更新 ans 
		while(pos[i] + mx < v[a[i]].size() && v[a[i]][pos[i] + mx] <= r) ans = a[i], mx++;//如果大于 mx 次，更新 ans 
	}
	for(int i = L[bl[r]]; i <= r; i++){//右邊不完整塊 
		if(pos[i] - mx + 1 >= 0 && v[a[i]][pos[i] - mx + 1] >= l){
			if(a[i] < ans) ans = a[i];
		}
		while(pos[i] - mx >= 0 && v[a[i]][pos[i] - mx] >= l) ans = a[i], mx++;
	}
	return ans;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	int q;
	cin >> n >> q;
	B = sqrt(n);
	for(int i = 1; i <= n; i++) cin >> a[i], b[i] = a[i];
	
	sort(b + 1, b + n + 1);
	int m = unique(b + 1, b + n + 1) - b - 1;
	for(int i = 1; i <= n; i++) a[i] = lower_bound(b + 1, b + m + 1, a[i]) - b;//離散化 
	for(int i = 1; i <= n; i++) v[a[i]].push_back(i), pos[i] = v[a[i]].size() - 1;
	
	for(int i = 1; i <= n; i++) bl[i] = (i - 1) / B + 1;
	for(int i = 1; i <= n; i++) R[bl[i]] = i;
	for(int i = n; i >= 1; i--) L[bl[i]] = i;
	tot = (n - 1) / B + 1;//分塊預處理 
	
	for(int i = 1; i <= tot; i++) init(i);//預處理 f 數組 
	
	int x;
	for(int i = 1; i <= q; i++){
		int l, r;
		cin >> l >> r;
		l = (l + x - 1) % n + 1;
		r = (r + x - 1) % n + 1;
		if(l > r) swap(l, r);
		x = b[query(l, r)];
		cout << x << "\n";
	}
	return 0;
}