不用管它随机什么的，就用贪心的思想去想，
会发现这道题的实质是：求查询区间众数出现次数。
莫队即可解决。
注意字符集1e9，要离散化处理。
1 #include2 3 using namespace std; 4 5 #define re register 6 #define rep(i, a, b) for (re int i = a; i <= b; ++i) 7 #define repd(i, a, b) for (re int i = a; i >= b; --i) 8 #define maxx(a, b) a = max(a, b); 9 #define minn(a, b) a = min(a, b);10 #define LL long long11 #define INF (1 << 30)12 13 inline int read() {14 int w = 0, f = 1; char c = getchar();15 while (!isdigit(c)) f = c == '-' ? -1 : f, c = getchar();16 while (isdigit(c)) w = (w << 3) + (w << 1) + (c ^ '0'), c = getchar();17 return w * f;18 }19 20 const int maxn = 2e5 + 5;21 22 struct Query {23 int l, r, id, pos;24 } q[maxn];25 bool cmp(Query a, Query b) { return a.pos < b.pos || a.pos == b.pos && a.r < b.r; }26 27 struct Value {28 int v, id;29 } v[maxn];30 bool cmpv(Value a, Value b) { return a.v < b.v; }31 32 int a[maxn], b[maxn], l[maxn], cnt[maxn], n, m, size;33 34 int main() {35 n = read(), m = read();36 size = sqrt(n);37 rep(i, 1, n) v[i].v = read(), v[i].id = i;38 sort(v+1, v+n+1, cmpv);39 a[v[1].id] = 1;40 rep(i, 2, n) a[v[i].id] = a[v[i-1].id] + (v[i].v == v[i-1].v ? 0 : 1);41 42 rep(i, 1, m) q[i].l = read(), q[i].r = read(), q[i].id = i, q[i].pos = (q[i].l + size - 1) / size;43 sort(q+1, q+m+1, cmp);44 int pl = 1, pr = 0, ans = 0; l[0] = maxn;45 rep(i, 1, m) {46 while (pl < q[i].l) l[cnt[a[pl]]]--, l[cnt[a[pl]]-1]++, cnt[a[pl++]]--;47 while (pl > q[i].l) cnt[a[--pl]]++, l[cnt[a[pl]]]++, l[cnt[a[pl]]-1]--, maxx(ans, cnt[a[pl]]);48 while (pr < q[i].r) cnt[a[++pr]]++, l[cnt[a[pr]]]++, l[cnt[a[pr]]-1]--, maxx(ans, cnt[a[pr]]);49 while (pr > q[i].r) l[cnt[a[pr]]]--, l[cnt[a[pr]]-1]++, cnt[a[pr--]]--;50 while (!l[ans]) ans--;51 b[q[i].id] = ans;52 }53 rep(i, 1, m) printf("%d\n", -b[i]);54 return 0;55 }