NKOJ 2751 蒲公英（分块）

发表于 |
字数统计: 1,170字 | 阅读时长 ≈ 6min

P2751【Violet VI】蒲公英

问题描述

在乡下的小路旁种着许多蒲公英，而我们的问题正是与这些蒲公英有关。
为了简化起见，我们把所有的蒲公英看成一个长度为n的序列(a1,a2,a3,a4,…an),
其中ai为一个正整数，表示第i棵蒲公英的种类编号。
而每次询问一个区间[l,r],你需要回答区间里出现次数最多的是哪种蒲公英，如果有
若干种蒲公英出现次数相同,则输出种类编号最小的那个。
注意，你的算法必须是在线的。

输入格式

第一行两个整数n,m，表示有n株蒲公英，m次询问。
接下来一行 n 个空格分隔的整数ai，表示蒲公英的种类
再接下来m行每行两个整数l0,r0,我们令上次询问的结果为x（如果这是第一次询问，则x=0)。
令l=(l0+x-1)mod n +1,r=(r0+x-1)mod n +1,如果l>r，则交换l,r。
最终的询问区间为[l,r]。

输出格式

输出m行。每行一个整数，表示每次询问的结果。

样例输入

6 3
1 2 3 2 1 2
1 5
3 6
1 5

样例输出

1
2
1

提示

对于 20% 的数据，保证1<=n,m<=3000。
对于 100% 的数据，保证1<=n<=40000，1<=m<=50000，1<=ai<=10^9

区间众数问题，分块的经典解法，两种处理方法

做法一：
分成$n^{\frac {1}{3}}$块，预处理$B[i][j]$表示第$i$块到第$j$块的信息，维护每个数出现的次数，并记录区间众数。
查询的时候，先找到覆盖的最大整块区间$[L,R]$将$B[L][R]$复制出来，然后将两边剩下的数暴力插入。
复杂度$O(n^{\frac{5}{3}})$

做法二：
分成$\sqrt{n}$块，预处理$A[i][j]$表示第$i$块到第$j$块中的众数，并记录众数的出现次数
查询的时候，同样找到区间$[L,R]$，答案只可能是$A[L][R]$或两侧剩下的数，枚举两侧剩下的数，然后查询一下他在区间中出现的次数，更新答案即可。
关于查询一个数在区间中的出现次数，可以用vector记下每个数出现位置然后二分查找，复杂度$O(n\sqrt{n}log_2{n})$
或者预处理$S[i][j][k]$，表示第$i$块中，前$j$个位置，数字$k$出现次数，$SS[i][k]$，表示前$i$块中，数字$k$出现的次数，然后查询的时候就可以直接用了（$S$可以不用处理，每次暴力跑一边两边剩下的数就行了），由于每块最多$\sqrt{n}$个数，因此预处理的时空复杂度都是$O(n\sqrt{n})$，总时间复杂度也是$O(n\sqrt{n})$

做法一代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#define N 50005
using namespace std;
struct node
{
	int a,b,c[N];
	void Ins(int x)
	{
		c[x]++;
		if(c[x]>b||(c[x]==b&&x<a))a=x,b=c[x];
	}
	void Del(int x){c[x]--;}
}C[40][40],tmp;
int n,m,A[N],B[N],id[N],lp[N],rp[N],S,Cnt;
int GS(int l,int r)
{
	int i,j,k,x,y,p,q;
	if(id[l]==id[r])
	{
		for(i=l;i<=r;i++)tmp.Ins(A[i]);
		k=tmp.a;tmp.a=tmp.b=0;
		for(i=l;i<=r;i++)tmp.Del(A[i]);
		return B[k];
	}
	x=id[l]+1;y=id[r]-1;
	p=C[x][y].a;q=C[x][y].b;
	for(i=l;i<lp[x];i++)C[x][y].Ins(A[i]);
	for(i=rp[y]+1;i<=r;i++)C[x][y].Ins(A[i]);
	k=C[x][y].a;C[x][y].a=p;C[x][y].b=q;
	for(i=l;i<lp[x];i++)C[x][y].Del(A[i]);
	for(i=rp[y]+1;i<=r;i++)C[x][y].Del(A[i]);
	return B[k];
}
int main()
{
	int i,j,k,x,y,ans=0;
	scanf("%d%d",&n,&m);
	for(i=1;i<=n;i++)scanf("%d",&A[i]),B[i]=A[i];
	sort(B+1,B+n+1);
	for(i=1;i<=n;i++)A[i]=lower_bound(B+1,B+n+1,A[i])-B;
	S=pow(n,2.0/3);j=1;
	for(i=1;i<=n;i++)
	{
		id[i]=i%S?j:j++;
		if(!lp[id[i]])lp[id[i]]=i;
		rp[id[i]]=max(rp[id[i]],i);
		Cnt=max(Cnt,id[i]);
	}
	for(i=1;i<=Cnt;i++)
	for(j=i;j<=Cnt;j++)
	for(k=lp[i];k<=rp[j];k++)C[i][j].Ins(A[k]);
	for(i=1;i<=m;i++)
	{
		scanf("%d%d",&x,&y);
		x=(x+ans-1)%n+1;
		y=(y+ans-1)%n+1;
		if(x>y)swap(x,y);
		ans=GS(x,y);
		printf("%d\n",ans);
	}
}