洛谷 P4168 [Violet]蒲公英（算法竞赛进阶指南，分块, 离散化）

算法竞赛进阶指南， 227页，分块, 离散化

本题要点：

1、先离散化，编号的大小为 10^9, 而元素个数为 5 * 10^5

2、 分块，将 n 个数值，平均分为 sqrt(n * log(n)) 段。 f[i][j]表示从第i段到第j段，出现最多的蒲公英编号。

3、数组 f[T][T]的计算，详细看代码。

4、 假如区间 [l ,r] 包含3 部分，中间是若干完整的段 [L, R]，两边是不完整的段 [l, L), (R, r] ,

那么中间部分，直接得到出现最多的是哪个编号（f[L][R]）， 并计算出其出现过的次数。

扫描左右两边的两个不完整段，所有出现过的编号，计算每一个编号出现过的次数。

取以上出现过的最多次数，就是答案。

5、 计算某个编号 x 在 区间 [l, r] 出现的次数：

在序列 e[x] 中查找第一个大于等于l 的下标 ，lower_bound(e[x].begin(), e[x].end(), l);

在序列 e[x] 中查找第一个大于r 的下标, upper_bound(e[x].begin(), e[x].end(), r);

两个值相减即可;

#include <cmath>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#include <iostream>
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];
//L[N], R[N]分别表示每一段的左端点，右端点; pos[i] 表示 点i所在的段的编号
// f[i][j]表示从第i段到第j段，出现最多的蒲公英编号 
vector<int> e[N];	// e[i]表示数值i 在序列中出现的下标
int n, m, t;

void discrete()
{
	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 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;
	}
	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);	
	}
	if(f[x][y])
	{
		work(f[x][y], l, r, ans, cnt);
	}
	return b[ans];
}

int main()
{
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= n; ++i)
	{
		scanf("%d", &a[i]);
	}
	discrete();
	t = sqrt(log(n) / log(2) * n);	//一共有t段
	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)
	{
		++t, L[t] = R[t - 1] + 1, R[t] = n;
	}
	for(int i = 1; i <= t; ++i)
		for(int j = L[i]; j <= R[i]; ++j)
		{
			pos[j] = i;		//坐标 j所在哪一段
		}
	memset(f, 0, sizeof f);
	for(int i = 1; i <= t; ++i)	
	{
		memset(c, 0, sizeof c);	//数组c[i] 表示数值i出现的次数
		int cnt = 0, ans = 0;	//cnt 表示出现的次数，ans表示这个数是多少
		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 left, right, x = 0;
	while(m--)
	{
		scanf("%d%d", &left, &right);
		left = (left + x - 1) % n + 1;
		right = (right + x -1) % n + 1;
		if(left > right)	swap(left, right);
		x = ask(left, right);
		printf("%d\n", x);
	}
	return 0;
}

/*
6 3 
1 2 3 2 1 2 
1 5 
3 6 
1 5
*/

/*
1 
2 
1
*/