蒲公英

Description

我们把所有的蒲公英看成一个长度为\(n\)的序列(\(a_1,a_2,...a_n\))，其中\(a_i\)为一个正整数，表示第i棵蒲公英的种类的编号。

每次询问一个区间\([l,r]\)，你需要回答区间里出现次数最多的是哪种蒲公英，如果有若干种蒲公英出现次数相同，则输出种类编号最小的那个。

注意，你的算法必须是在线的。

Input Data

第一行两整数\(n,m\)，表示有\(n\)棵蒲公英，mm次询问。

接下来一行\(n\)个空格分隔的整数\(a_i\)，表示蒲公英的种类。

接下来\(m\)行，每行两个整数\(l_0,r_0\)。令上次的查询结果为\(x\)（如果是第一次查询，则\(x=0\)）。

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

Output Data

输出\(m\)行，每行一个整数，表示每次查询的结果。

Input / Output Sample

6 3

1 2 3 2 1 2

1 5

3 6

1 5

Data Limit

\(n \le 40000,m \le 50000,1 \le a_i \le 10^9n≤40000,m≤50000,1≤ai≤10^9\)

Problem Source

\(BZOJ2724\)

算法竞赛进阶指南\(P218-219\)

这道题和\(数列分块入门9\)蜜汁相似QAQ。

请自行参照我的\(数列分块入门9题解\)

这里仅放上代码QAQ——

代码

#include<bits/stdc++.h>

using namespace std;

#define MAXN 40005

int n, m, T;

int a[MAXN], b[MAXN], c[MAXN];

int d, f[2000][2000];

int s[MAXN];

vector<int> p[MAXN];

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

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

}

int Get( int l, int r ){

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

		int ans1(0), ans2(0);

		for ( int i = l; i <= r; ++i ){

			int t(Count( l, r, a[i] ));

			if ( t > ans2 ) ans1 = a[i], ans2 = t;

			if ( t == ans2 ) ans1 = min( ans1, a[i] );

		}

		return ans1;

	}

	int ans1(f[b[l] + 1][b[r] - 1]), ans2(Count( l, r, ans1 ));

	for ( int i = l; b[l] == b[i]; ++i ){

		int t(Count( l, r, a[i] ));

		if ( t > ans2 ) ans1 = a[i], ans2 = t;

		if ( t == ans2 ) ans1 = min( ans1, a[i] );

	}

	for ( int i = r; b[r] == b[i]; --i ){

		int t(Count( l, r, a[i] ));

		if ( t > ans2 ) ans1 = a[i], ans2 = t;

		if ( t == ans2 ) ans1 = min( ans1, a[i] );

	}

	return ans1;

}

int main(){

	scanf( "%d%d", &n, &T );

	d = 0;

	while( ( 1 << d ) <= n ) d++;

	d = (int)( n / sqrt( 2 * T * d ) );

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

		scanf( "%d", &a[i] ); c[i] = a[i]; b[i] = ( i - 1 ) / d + 1;

	}

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

	m = unique( c + 1, c + n + 1 ) - c - 1;

	for ( int i = 1; i <= n; ++i ) a[i] = lower_bound( c + 1, c + m + 1, a[i] ) - c;

	for ( int i = 1; i <= n; ++i ) p[a[i]].push_back(i);

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

		memset( s, 0, sizeof s );

		int ans1(0), ans2(0);

		for ( int j = ( i - 1 ) * d + 1; j <= n; ++j ){

			s[a[j]]++;

			if ( s[a[j]] == ans2 ) ans1 = min( ans1, a[j] );

			if ( s[a[j]] > ans2 ) ans1 = a[j], ans2 = s[a[j]];

			if ( b[j + 1] != b[j] ) f[i][b[j]] = ans1;

		}

	}

	int x(0);

	while( T-- ){

		int l, r;

		scanf( "%d%d", &l, &r );

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

		int t(min( l, r )); r = max( l, r ); l = t;

		printf( "%d\n", x = c[Get( l, r )] );

	}

	return 0;

}