处理关于区间众数的问题

这个题意思就是处理区间众数，区间想到只有线段树，但是线段树做不了一点，所以考虑暴力其他数据结构。

---

这里引入一个思想叫做分块，把数列分成一块一块，然后分别维护每块中间的信息。

对于修改，直接修改区间中整块内和散块的信息（虽然这题没有）。对于查询，就直接可以处理整块信息，然后再处理散块信息。

没错，就是这个非常暴力的思想。一般块长开到 $\sqrt{n}$，这样过线段树模板题，时间复杂度 $O(n \sqrt{n})$。

分块可以支持动态的，但对于本题是静态问题分块可以支持的就更多了。就比如这个区间众数。

---

先考虑对于一个区间众数有可能是哪些数。

可能是区间整块内的数的众数（这个可以预处理），也可能是块外的数。

我们预处理 d[i][j] 表示 i 块到 j 块内的众数，和 sm[i][j] 表示前 i 个块内 j 出现了几次。

这两个可以 $O(n \sqrt{n})$ 预处理的，直接扫一遍就可以了。

for (int i=1;i<=n;++i){//处理d和sm 
	if (i==1 || idx[i]!=idx[i-1]){//块的起点 
		mx=n+1145,cnt=0;
		for (int j=0;j<N;++j)
			tot[j]=0;//memset 
		for (int j=i;j<=n;++j){
			++tot[a[j]];
			if (tot[a[j]]>cnt || (tot[a[j]]==cnt && qaq[mx]>qaq[a[j]])/*选最小*/)
				mx=a[j],cnt=tot[a[j]];
			if (j==n || idx[j]!=idx[j+1]){//块的后面
				d[idx[i]][idx[j]]=d[idx[j]][idx[i]]=mx;
				if (i==1)
					for (int k=0;k<N;++k)
						sm[idx[j]][k]=tot[k];
			}
		} 
	}
}

然后呢？查询就直接暴力扫一遍块外的数，然后记录每一种数出现次数，和区间内众数出现比较，那个大哪个就是答案。

代码：

for (int _=0;_<m;++_){
	scanf("%d%d",&l,&r);
	l=(l+x-1)%n+1,r=(r+x-1)%n+1;
	if (l>r){
		swap(l,r);
	}
	idx1=idx[l],idx2=idx[r];
	if (idx1==idx2 || idx1+1==idx2){
		mx=n+1145,cnt=0;
		for (int i=l;i<=r;++i)
			++tot[a[i]];
		for (int i=l;i<=r;++i){
			if (tot[a[i]]>cnt || (tot[a[i]]==cnt && qaq[mx]>qaq[a[i]]))
				mx=a[i],cnt=tot[a[i]];
			tot[a[i]]=0;
		}
		put(mx);
		x=qaq[mx];
		continue;
	}
	for (int i=l;idx[i]==idx1;++i){
		if (tot[a[i]]==0){
			tot[a[i]]+=sm[idx2-1][a[i]]-sm[idx1][a[i]];//加上前缀和 
		}
		++tot[a[i]];
	}
	for (int i=r;idx[i]==idx2;--i){
		if (tot[a[i]]==0){
			tot[a[i]]+=sm[idx2-1][a[i]]-sm[idx1][a[i]];//加上前缀和 
		}
		++tot[a[i]];
	}
	mx=n+1145,cnt=0;
	for (int i=l;idx[i]==idx1;++i){
		if (tot[a[i]]>cnt || (tot[a[i]]==cnt && qaq[mx]>qaq[a[i]]))
			mx=a[i],cnt=tot[a[i]];
		tot[a[i]]=0;
	}
	for (int i=r;idx[i]==idx2;--i){
		if (tot[a[i]]>cnt || (tot[a[i]]==cnt && qaq[mx]>qaq[a[i]]))
			mx=a[i],cnt=tot[a[i]];
		tot[a[i]]=0;
	}
	num=d[idx1+1][idx2-1];
	if (sm[idx2-1][num]-sm[idx1][num]>cnt || 
	(sm[idx2-1][num]-sm[idx1][num]==cnt && qaq[mx]>qaq[num])){
		mx=num;
	}
	x=qaq[mx];
	put(mx);
}

然后就没了。