CF840D Destiny()

观察到 \(2\le k\le5\),于是复杂度主要就是和 \(r-l+1\) 有关,来对 \(r-l+1\) 做根号分治,取阈值 \(lim\)。

对于 \(r-l+1\le lim\),暴力遍历 \(l\sim r\),同时维护出现次数的桶,复杂度 \(O(lim)\)。

对于 \(r-l+1\gt lim\),

  • 先找到出现次数大于 \(\dfrac 15lim\) 的数,(最多有 \(\dfrac n{\frac 15lim}\) 个),记录一下(只有这些数可能产生答案)
  • 对于每一个数 \(x\),先计算 \(cnt\) 数组代表其出现次数的前缀和(出现次数是一个 \(01\) 数组,将其前缀和)。
  • 然后遍历每一个询问 \(l,r,k\),计算 \(x\) 在这个区间的出现次数(前缀和之后差分),如果大于 \(\dfrac {r-l+1}k\),就记录下来。

复杂度是 \(\max\{O(\dfrac n{\frac 15lim}),O(lim)\}\),理论的 \(lim\) 最佳取值是 \(\sqrt{5n}\)。

#include<stdio.h>
#include<math.h>

const int N = 3e5 + 5;
const int inf = 2e9;

int n,m,lim,vlim,a[N],buc[N],cc[N],cnt[N];
int ql[N],qr[N],qx[N],qa[N];

int main(){
	scanf("%d%d",&n,&m);
	lim = sqrt(5 * n); vlim = lim / 5; 
	for(int i = 1;i <= n;++i) scanf("%d",a + i),++cc[a[i]];
	for(int i = 1;i <= m;++i){
		int l,r,k;
		scanf("%d%d%d",&l,&r,&k);
		int x = (r - l + 1) / k + 1;
		if(r - l + 1 <= lim){
			qa[i] = inf;
			for(int j = l;j <= r;++j){
				++buc[a[j]];
				if(buc[a[j]] >= x)
					qa[i] = min(qa[i],a[j]);
			}
			if(qa[i] == inf) qa[i] = -1;
			for(int j = l;j <= r;++j) --buc[a[j]];
		}
		ql[i] = l; qr[i] = r; qx[i] = x;
	}
	for(int j = 1;j <= n;++j){
		if(cc[j] < vlim) continue;
		for(int i = 1;i <= n;++i)
			cnt[i] = cnt[i - 1] + (a[i] == j);
		for(int i = 1;i <= m;++i){
			if(qa[i]) continue;
			int x = cnt[qr[i]] - cnt[ql[i] - 1];
			if(x >= qx[i]) qa[i] = j;
		}
	}
	for(int i = 1;i <= m;++i)
		printf("%d\n",qa[i] ? qa[i] : -1);
	return 0;
}
————————

观察到 \(2\le k\le5\),于是复杂度主要就是和 \(r-l+1\) 有关,来对 \(r-l+1\) 做根号分治,取阈值 \(lim\)。

对于 \(r-l+1\le lim\),暴力遍历 \(l\sim r\),同时维护出现次数的桶,复杂度 \(O(lim)\)。

对于 \(r-l+1\gt lim\),

  • 先找到出现次数大于 \(\dfrac 15lim\) 的数,(最多有 \(\dfrac n{\frac 15lim}\) 个),记录一下(只有这些数可能产生答案)
  • 对于每一个数 \(x\),先计算 \(cnt\) 数组代表其出现次数的前缀和(出现次数是一个 \(01\) 数组,将其前缀和)。
  • 然后遍历每一个询问 \(l,r,k\),计算 \(x\) 在这个区间的出现次数(前缀和之后差分),如果大于 \(\dfrac {r-l+1}k\),就记录下来。

复杂度是 \(\max\{O(\dfrac n{\frac 15lim}),O(lim)\}\),理论的 \(lim\) 最佳取值是 \(\sqrt{5n}\)。

#include<stdio.h>
#include<math.h>

const int N = 3e5 + 5;
const int inf = 2e9;

int n,m,lim,vlim,a[N],buc[N],cc[N],cnt[N];
int ql[N],qr[N],qx[N],qa[N];

int main(){
	scanf("%d%d",&n,&m);
	lim = sqrt(5 * n); vlim = lim / 5; 
	for(int i = 1;i <= n;++i) scanf("%d",a + i),++cc[a[i]];
	for(int i = 1;i <= m;++i){
		int l,r,k;
		scanf("%d%d%d",&l,&r,&k);
		int x = (r - l + 1) / k + 1;
		if(r - l + 1 <= lim){
			qa[i] = inf;
			for(int j = l;j <= r;++j){
				++buc[a[j]];
				if(buc[a[j]] >= x)
					qa[i] = min(qa[i],a[j]);
			}
			if(qa[i] == inf) qa[i] = -1;
			for(int j = l;j <= r;++j) --buc[a[j]];
		}
		ql[i] = l; qr[i] = r; qx[i] = x;
	}
	for(int j = 1;j <= n;++j){
		if(cc[j] < vlim) continue;
		for(int i = 1;i <= n;++i)
			cnt[i] = cnt[i - 1] + (a[i] == j);
		for(int i = 1;i <= m;++i){
			if(qa[i]) continue;
			int x = cnt[qr[i]] - cnt[ql[i] - 1];
			if(x >= qx[i]) qa[i] = j;
		}
	}
	for(int i = 1;i <= m;++i)
		printf("%d\n",qa[i] ? qa[i] : -1);
	return 0;
}