「Violet」蒲公英

传送门

区间众数，强制在线。

分块经典题。

像这题一样预处理，然后就直接爆搞，复杂度 \(O(n \sqrt n)\)
参考代码：
#include <algorithm>

#include <cstdio>

#include <cmath>

#define rg register

#define file(x) freopen(x".in", "r", stdin), freopen(x".out", "w", stdout)

using namespace std;

template < class T > inline void read(T& s) {

	s = 0; int f = 0; char c = getchar();

	while ('0' > c || c > '9') f |= c == '-', c = getchar();

	while ('0' <= c && c <= '9') s = s * 10 + c - 48, c = getchar();

	s = f ? -s : s;

}

const int _ = 40005, __ = 205;

int n, q, len, a[_], X[_], cnt[_], Q[_];

int m, pos[_], f[__][__], c[__][_];

inline int Query(int l, int r) {

	int res, num;

	if (pos[l] == pos[r]) {

		res = num = 0;

		for (rg int k = l; k <= r; ++k) {

			++cnt[a[k]];

			if (num < cnt[a[k]] || (num == cnt[a[k]] && a[k] < res))

				num = cnt[a[k]], res = a[k];

		}

		for (rg int i = l; i <= r; ++i) cnt[a[i]] = 0;

	} else {

		res = f[pos[l] + 1][pos[r] - 1], num = c[pos[r] - 1][res] - c[pos[l]][res];

		Q[0] = 0;

		for (rg int i = l; i <= pos[l] * m && i <= n; ++i) Q[++Q[0]] = a[i];

		for (rg int i = (pos[r] - 1) * m + 1; i <= r; ++i) Q[++Q[0]] = a[i];

		for (rg int i = 1; i <= Q[0]; ++i) {

			if (cnt[Q[i]] == 0)

				cnt[Q[i]] = c[pos[r] - 1][Q[i]] - c[pos[l]][Q[i]];

			++cnt[Q[i]];

			if (num < cnt[Q[i]] || (num == cnt[Q[i]] && res > Q[i]))

				num = cnt[Q[i]], res = Q[i];

		}

		for (rg int i = 1; i <= Q[0]; ++i) cnt[Q[i]] = 0;

	}

	return res;

}

int main() {

#ifndef ONLINE_JUDGE

	file("cpp");

#endif

	read(n), read(q), m = sqrt(1.0 * n);

	for (rg int i = 1; i <= n; ++i) read(a[i]), X[i] = a[i], pos[i] = (i - 1) / m + 1;

	sort(X + 1, X + n + 1);

	len = unique(X + 1, X + n + 1) - X - 1;

	for (rg int i = 1; i <= n; ++i) a[i] = lower_bound(X + 1, X + len + 1, a[i]) - X;

	for (rg int i = 1; i <= pos[n]; ++i) {

		for (rg int j = 1; j <= len; ++j) c[i][j] = c[i - 1][j];

		for (rg int j = (i - 1) * m + 1; j <= i * m; ++j) ++c[i][a[j]];

	}

	int res, num;

	for (rg int i = 1; i <= pos[n]; ++i)

		for (rg int j = i; j <= pos[n]; ++j) {

			res = f[i][j - 1], num = c[j - 1][res] - c[i - 1][res];

			for (rg int k = (j - 1) * m + 1; k <= j * m; ++k) {

				if (cnt[a[k]] == 0)

					cnt[a[k]] = c[j - 1][a[k]] - c[i - 1][a[k]];

				++cnt[a[k]];

				if (num < cnt[a[k]] || (num == cnt[a[k]] && res > a[k]))

					num = cnt[a[k]], res = a[k];

			}

			f[i][j] = res;

			for (rg int k = (j - 1) * m + 1; k <= j * m; ++k) cnt[a[k]] = 0;

		}

	for (rg int ans = 0, l, r; q--; ) {

		read(l), l = (l + ans - 1) % n + 1;

		read(r), r = (r + ans - 1) % n + 1;

		if (l > r) swap(l, r);

		ans = X[Query(l, r)], printf("%d\n", ans);

	}

	return 0;

}
巴特西

「Violet」蒲公英

「Violet」蒲公英

最新文章

热门文章
