[BZOJ2724][Violet 6]蒲公英

试题描述

输入

修正一下

l = (l_0 + x - 1) mod n + 1, r = (r_0 + x - 1) mod n + 1

输出

输入示例

输出示例

数据规模及约定

修正下：

n <= 40000, m <= 50000

题解

分块，先预处理出 f[i][j] 表示第 i 块到第 j 块的众数，枚举起点 i 然后扫一遍就好了。

其次是询问，对于一个询问 [ql, qr]，其中 ql 属于块 l，qr 属于块 r，众数要么是 f[l+1][r-1]，要么是不完整块中的数，所以我们需要搞一个 calc(l, r, x) 功能，表示询问 [l, r] 中 x 出现的次数，有了这个功能后就可以做到把答案初始设为 f[l+1][r-1]（O(1)），然后 O(sqrt(n)) 暴力枚举不完整块中的数，如果出现次数比当前的多，就更新答案。

这个 calc() 函数可以这样搞：把所有数离散，每个数的位置记下来，然后当询问 calc(l, r, x) 在 x 的位置序列上二分一下就可以计算了。

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <algorithm>

#include <cmath>

#include <vector>

using namespace std;

const int BufferSize = 1 << 16;

char buffer[BufferSize], *Head, *Tail;

inline char Getchar() {

    if(Head == Tail) {

        int l = fread(buffer, 1, BufferSize, stdin);

        Tail = (Head = buffer) + l;

    }

    return *Head++;

}

int read() {

    int x = 0, f = 1; char c = Getchar();

    while(!isdigit(c)){ if(c == '-') f = -1; c = Getchar(); }

    while(isdigit(c)){ x = x * 10 + c - '0'; c = Getchar(); }

    return x * f;

}

#define maxn 40010

#define maxq 210

int n, m, num[maxn], A[maxn], st[maxq], en[maxq], bl[maxn], cntb, f[maxq][maxq], cntn[maxn];

vector <int> pos[maxn];

int calc(int l, int r, int x) {

	return upper_bound(pos[x].begin(), pos[x].end(), r) - lower_bound(pos[x].begin(), pos[x].end(), l);

}

int query(int ql, int qr) {

	int l = bl[ql], r = bl[qr];

	if(r - l <= 1) {

		int ans = A[ql], mx = calc(ql, qr, ans);

		for(int i = ql + 1; i <= qr; i++) {

			int tmp = calc(ql, qr, A[i]);

			if(mx < tmp || (mx == tmp && ans > A[i])) ans = A[i], mx = tmp;

		}

		return ans;

	}

	int ans = f[l+1][r-1], mx = calc(ql, qr, ans);

	for(int i = ql; i <= en[l]; i++) {

		int tmp = calc(ql, qr, A[i]);

		if(mx < tmp || (mx == tmp && ans > A[i])) ans = A[i], mx = tmp;

	}

	for(int i = st[r]; i <= qr; i++) {

		int tmp = calc(ql, qr, A[i]);

		if(mx < tmp || (mx == tmp && ans > A[i])) ans = A[i], mx = tmp;

	}

	return ans;

}

int main() {

	n = read(); m = read();

	int siz = (int)sqrt(n + .5);

	for(int i = 1; i <= n; i++) {

		num[i] = A[i] = read();

		int p = (i - 1) / siz + 1; cntb = p;

		if(!st[p]) st[p] = i;

		en[p] = i;

		bl[i] = p;

	}

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

	for(int i = 1; i <= n; i++) A[i] = lower_bound(num + 1, num + n + 1, A[i]) - num;

	for(int i = 1; i <= cntb; i++) {

		memset(cntn, 0, sizeof(cntn));

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

			cntn[A[j]]++;

			int r = bl[j];

			if(r > i && !f[i][r]) f[i][r] = f[i][r-1];

			if(!f[i][r] || cntn[f[i][r]] < cntn[A[j]] || (cntn[f[i][r]] == cntn[A[j]] && f[i][r] > A[j]))

				f[i][r] = A[j];

		}

	}

	for(int i = 1; i <= n; i++) pos[A[i]].push_back(i);

	int x = 0;

	while(m--) {

		int l = (read() + x - 1) % n + 1, r = (read() + x - 1) % n + 1;

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

		int tmp = query(l, r);

		printf("%d\n", num[tmp]);

		x = num[tmp];

	}

	return 0;

}

巴特西

[BZOJ2724][Violet 6]蒲公英

最新文章

热门文章