「Destiny」Solution

本文主要是介绍「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 registerchar 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;
}

这篇关于「Destiny」Solution的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---