「Destiny」Solution

简述题意

给定 $n$ 个元素，$q$ 次询问。
每次给出三个参数 $l,r,k$，询问区间 $[l,r]$ 内是否存在出现次数严格大于 $\frac{r-l+1}{k}$ 的数。如果有，输出最小的那个数，否则输出 $-1$。

• $1\le n,q\le 3\times 10^5$，$1\le a_i\le n$，$2\le k\le 5$。

思路

注意到，出现次数随着区间长度增大而增大。也就意味着，对于长度很大的区间，可能满足条件的数不会有太多个，这启发我们根号分治。

不妨令 $len=r-l+1$，表示区间长度。

• $len\le \sqrt{n}$，直接暴力枚举区间，统计区间内每个数出现的次数即可。
• $len>\sqrt{n}$，由于 $k$ 最大为 $5$，所以这个数在 $[l,r]$ 中至少出现 $\frac{\sqrt{n}}{5}$ 次，也就意味着其在整个序列中也需要至少出现 $\frac{\sqrt{n}}{5}$ 次，而这样的数最多不超过 $5\times \sqrt{n}$，直接暴力枚举判断即可。

时间复杂度大致为 $O(\sqrt{n}\times q+5\times \sqrt{n}\times q)$

然而，显而易见：如果直接取 $\sqrt{n}$，前缀数组肯定是开不下的，经过多次测试（一顿乱试 ），根号分治的临界值取 $3500$ 可以卡过去，因为此时只需要考虑出现次数大于 $\frac{3500}{5}$ 的数，最多不会超过 $\frac{n}{700}$ 个（大概是 $429$ 个）。

代码

相当于 —— 优雅的暴力。
注意加上读优写优。

#include <bits/stdc++.h>
#define siz 3500
using namespace std;
const int MAXN = 3e5 + 5;
int n , q , a[MAXN] , cnt[MAXN] , idx , rk[MAXN] , pre[MAXN][429];
vector<int> vt;
namespace IO{
    #define il inline
    #define Re register
	char B[1 << 15], *S = B, *T = B , obuf[1 << 15] , *p3 = obuf;
	#define getchar() (S == T && (T = (S = B) + fread(B, 1, 1 << 15, stdin), S == T) ? EOF : *S++)
	#define putchar(x) (p3-obuf<1 << 15)?(*p3++=x):(fwrite(obuf,p3-obuf,1,stdout),p3=obuf,*p3++=x)
	template<typename item>
	il void read(Re item &x) {
	    char c(getchar());
	    x = 0;
	    int f(1);
	    while (c < '0' || c > '9') {if (c == '-') f = -1;c = getchar();}
	    while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
	    x *= f;
	}
    il void readch(Re char &x) {
        x = getchar();
        while(x != 'L' && x != 'R') x = getchar();
    }
	template<typename item, typename ...Arg>
	il void read(item &tmp, Arg& ...tmps) {read(tmp);read(tmps...);}
	template<typename item>
	il void write(Re item x) {
		if (x < 0) {putchar('-') , x = -x;}
		if (x > 9) write(x / 10);
		putchar(x % 10 + '0');
	}
}
using namespace IO;
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr) , cout.tie(nullptr);
	read(n , q);
	for (int i = 1 ; i <= n ; i ++) {
		read(a[i]);
		cnt[a[i]] ++;
	}
	for (int i = 1 ; i <= n ; i ++) {
		if (cnt[i] >= 700) rk[i] = ++ idx , vt.push_back(i);
	}
	for (int i = 1 ; i <= n ; i ++) {
		for (int j = 1 ; j <= idx ; j ++) pre[i][j] = pre[i - 1][j];
		if (rk[a[i]]) pre[i][rk[a[i]]] ++;
	}
	while(q --) {
		int l , r , k , d;
		read(l , r , k);
		if ((r - l + 1) % k == 0) d = (r - l + 1) / k + 1;
		else d = (r - l + 1 + (k - 1)) / k;
		if(r - l + 1 <= siz) {
			for (int i = l ; i <= r ; i = -~i) cnt[a[i]] = 0;
			int ans = 1e9;
			for (int i = l ; i <= r ; i = -~i) {
				cnt[a[i]] ++;
				if (cnt[a[i]] >= d) ans = min(ans , a[i]);
			}
			write(ans == 1e9 ? -1 : ans) , putchar('\n');
		} else {
			int ans = -1;
			for (int v : vt) {
				int id = rk[v];
				if (pre[r][id] - pre[l - 1][id] >= d) {
					ans = v;
					break;
				}
			}
			write(ans) , putchar('\n');
		}
	}
	fwrite(obuf , p3 - obuf , 1 , stdout);
    return 0;
}