bzoj2724 - 蒲公英 (分块+区间众数)

客官°小女子只卖身不卖艺 2021-12-14 12:07 258阅读 0赞

题面：

## Description ##

![T2des_286_29.gif][]

## Input ##

![T2input_286_29.gif][]

修正一下

l = (l\_0 + x – 1) mod n + 1, r = (r\_0 + x – 1) mod n + 1

## Output ##

![T2output_285_29.gif][]

## HINT ##

![T2hint_285_29.gif][]

## 修正下： ##

## n <= 40000, m <= 50000 ##

## 分析： ##

## 在线区间众数的分块做法比较多，这里提供一个思路： ##

## 首先离散化。显然某个区间内的众数应该是完整的所有块的众数，和不完整块中出现的数。所以我们可以预处理f(i,j)表示第 i 块到第 j 块的众数（枚举 i 开个桶扫一遍）。 ##

## 那么只要能快速得出一个数在某个区间内出现次数即可，每次只要比较至多2√n+1个元素的出现次数，这题就解决了。由于没有修改，只要离散化以后，给每个数 x 开个vector，按顺序存下 x 出现的位置，每次询问 x 时把区间的左右端点放进对应 vector 二分一下即可。根据均值不等式，可以算出分块大小大概是√(n/logn)。 ##

## 参考：[http://hzwer.com/3582.html。][http_hzwer.com_3582.html] ##

## 代码： ##

#include<bits/stdc++.h>
    using namespace std;
    const int N = 40006, T = 806;
    int a[N], b[N], c[N], L[N], R[N], pos[N], f[T][T];
    vector<int> e[N];
    // 找出x在[l,r]内的出现次数
    int find(int x, int l, int r) {
    	return upper_bound(e[x].begin(), e[x].end(), r) - lower_bound(e[x].begin(), e[x].end(), l);
    }
    // 更新最大出现次数和最小众数
    void work(int x, int l, int r, int &ans, int &cnt) {
    	int w = find(x, l, r);
    	if (w > cnt || (w == cnt && x < ans)) {
    		cnt = w;
    		ans = x;
    	}
    }
    
    int ask(int l, int r) {
    	int p = pos[l], q = pos[r];
    	int ans = 0, cnt = 0;
    	// 同一块内
    	if (p == q) {
    		for (int i = l; i <= r; i++) work(a[i], l, r, ans, cnt);
    		return b[ans];// 注意离散化了 要返回原数组的值
    	}
    	int x = 0, y = 0;
    	// 相差一块特殊处理(因为没有完整的一块)
    	if (p + 1 <= q - 1) {
    		x = p + 1;
    		y = q - 1;
    	}
    	// [l,r]的众数只能来自于区间[L,R] 或者 出现在[l,L)和(R,r]之间的数
            // 枚举在[l,L)和(R,r]之间的数
    	for (int i = l; i <= R[p]; i++) work(a[i], l, r, ans, cnt);
    	for (int i = L[q]; i <= r; i++) work(a[i], l, r, ans, cnt);
    	// 考虑[L,R](一至多个完整的块可以利用预处理的结果)
    	if (f[x][y]) work(f[x][y], l, r, ans, cnt);
    	return b[ans];
    }
    
    int main() {
    	int n, m;
    	cin >> n >> m;
    	for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    	// 离散化
    	memcpy(b, a, sizeof(b));
    	sort(b + 1, b + n + 1);
    	int tot = unique(b + 1, b + n + 1) - (b + 1);
    	for (int i = 1; i <= n; i++) {
    		a[i] = lower_bound(b + 1, b + tot + 1, a[i]) - b;
    		e[a[i]].push_back(i);// 存储每个数出现的所有位置
    	}
    	int t = sqrt(log(n) / log(2) * n);// 块的个数
    	int len = t ? n / t : n;// 块的大小
    	for (int i = 1; i <= t; i++) {
    		L[i] = (i - 1) * len + 1;
    		R[i] = i * len;
    	}
    	if (R[t] < n) {
    		L[t+1] = R[t] + 1;
    		R[++t] = n;
    	}
    	// 预处理每个数所属的块
    	for (int i = 1; i <= t; i++)
    		for (int j = L[i]; j <= R[i]; j++)
    			pos[j] = i;
    	memset(f, 0, sizeof(f));
    	// 预处理f[i][j](第i个块到第j个块的最小众数)
    	for (int i = 1; i <= t; i++) {
    		memset(c, 0, sizeof(c));
    		int cnt = 0, ans = 0;
    		for (int j = L[i]; j <= n; j++) {
    			if (++c[a[j]] > cnt || (c[a[j]] == cnt && a[j] < ans)) {
    				cnt = c[a[j]];
    				ans = a[j];
    			}
    			f[i][pos[j]] = ans;
    		}
    	}
    	int x = 0;
    	while (m--) {
    		int l, r;
    		scanf("%d %d", &l, &r);
    		// 按题意作转换
    		l = (l + x - 1) % n + 1;
    		r = (r + x - 1) % n + 1;
    		if (l > r) swap(l, r);
    		x = ask(l, r);
    		printf("%d\n", x);
    	}
    	return 0;
    }

[T2des_286_29.gif]: http://www.lydsy.com/JudgeOnline/upload/201204/T2des%286%29.gif
[T2input_286_29.gif]: http://www.lydsy.com/JudgeOnline/upload/201204/T2input%286%29.gif
[T2output_285_29.gif]: http://www.lydsy.com/JudgeOnline/upload/201204/T2output%285%29.gif
[T2hint_285_29.gif]: http://www.lydsy.com/JudgeOnline/upload/201204/T2hint%285%29.gif
[http_hzwer.com_3582.html]: http://hzwer.com/3582.html