简述题意
给定
n
n
n 个元素,
q
q
q 次询问。
每次给出三个参数
l
,
r
,
k
l, r, k
l,r,k,询问区间
[
l
,
r
]
[l, r]
[l,r] 内是否存在出现次数严格大于
r
−
l
+
1
k
\frac{r - l + 1} {k}
kr−l+1 的数。如果有,输出最小的那个数,否则输出
−
1
-1
−1。
- 1 ≤ n , q ≤ 3 × 1 0 5 1\leq n, q\leq 3\times 10 ^ 5 1≤n,q≤3×105, 1 ≤ a i ≤ n 1\leq a_i\leq n 1≤ai≤n, 2 ≤ k ≤ 5 2\leq k\leq 5 2≤k≤5。
思路
注意到,出现次数随着区间长度增大而增大。也就意味着,对于长度很大的区间,可能满足条件的数不会有太多个,这启发我们根号分治。
不妨令 l e n = r − l + 1 len=r-l+1 len=r−l+1,表示区间长度。
- l e n ≤ n len \le \sqrt n len≤n,直接暴力枚举区间,统计区间内每个数出现的次数即可。
- l e n > n len > \sqrt n len>n,由于 k k k 最大为 5 5 5,所以这个数在 [ l , r ] [l,r] [l,r] 中至少出现 n 5 \dfrac{\sqrt n}{5} 5n 次,也就意味着其在整个序列中也需要至少出现 n 5 \dfrac{\sqrt n}{5} 5n 次,而这样的数最多不超过 5 × n 5 \times \sqrt n 5×n,直接暴力枚举判断即可。
时间复杂度大致为 O ( n × q + 5 × n × q ) O(\sqrt n \times q + 5 \times \sqrt n \times q) O(n×q+5×n×q)
然而,显而易见:如果直接取
n
\sqrt n
n,前缀数组肯定是开不下的,经过多次测试(一顿乱试 ),根号分治的临界值取
3500
3500
3500 可以卡过去,因为此时只需要考虑出现次数大于
3500
5
\dfrac{3500}{5}
53500 的数,最多不会超过
n
700
\dfrac{n}{700}
700n 个(大概是
429
429
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;
}