题意
给定长度为 $n$ 的数组 $a$。你要处理 $m$ 次询问，每次询问需要输出区间中出现次数严格大于区间长度一半的数，或者判断没有这样的数。
$1 \leq n, m \leq 5 \times 10^4$
题解
这里给出一种乱搞做法。
考虑在区间中随机 $k$ 次，如果区间中存在出现次数严格大于区间长度一半的数，那么每次随机选到这个数的概率至少是 $\dfrac12$。而如果随机 $k$ 次都没有找到这样的数，就判定为没有。
在最坏情况下，只有 $\dfrac1{2^k}$ 的概率答案错误。
代码
// Please submit with C++17! It's best to use C++20 or higher version.
// By Koicy (https://koicy.ly)
// rbtree (i@koicy.ly)
// I've reached the end of my illusion.
// #define EFILE ""
#include <algorithm>
#include <array>
#include <cmath>
#include <cstring>
#include <iomanip>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <utility>
#include <vector>
#define _CONSOLE 0
#define _MULTI_TESTS 0
using namespace std;
using tp = long long;
constexpr tp ZERO = 0, ONE = 1, INF32 = -1u >> 2, INF = -1ull >> 2;
// :\
namespace _IO {
constexpr size_t BUF = 217217;
unsigned long long h = 5;
char ibuf[BUF], obuf[BUF];
char *li, *ri, *lo = obuf, *ro = obuf + BUF, st[100], *tp = st;
FILE *Istream = stdin, *Ostream = stdout;
char GC() {
#if _CONSOLE
return getchar();
#endif
if (li == ri) {
li = ibuf; ri = li + fread(li, 1, BUF, Istream);
if (li == ri) return '\n';
}
return *li++;
}
void _flush() {
fwrite(obuf, 1, lo - obuf, Ostream);
lo = obuf;
}
void PC(char ch) {
#if _CONSOLE
return (void)putchar(ch);
#endif
if (lo == ro) _flush();
*lo++ = ch;
}
template <typename Type>
void r_int(Type& x) {
bool neg = 0;
char ch = GC();
while (ch < 48 || ch > 57) { neg ^= ch == 45; ch = GC(); }
for (x = 0; ch >= '0' && ch <= '9'; ch = GC()) x = x * 10 + (ch & 15);
if (neg) x = -x;
}
template <typename Type>
void r_uint(Type& x) {
char ch = GC();
while (ch < 48 || ch > 57) ch = GC();
for (x = 0; ch >= '0' && ch <= '9'; ch = GC()) x = x * 10 + (ch & 15);
}
template <typename Type>
void r_db(Type& x) {
bool neg = 0;
char ch = GC();
while (ch < 48 || ch > 57) { neg ^= ch == 45; ch = GC(); }
for (x = 0; ch >= '0' && ch <= '9'; ch = GC()) x = x * 10 + (ch & 15);
if (ch == '.') {
double p = 1;
for (ch = GC(); ch >= '0' && ch <= '9'; ch = GC()) x += (p /= 10) * (ch & 15);
}
if (neg) x = -x;
}
template <typename Type>
void w_uint(Type x) {
if (!x) { PC('0'); return; }
while (x) { *tp++ = x % 10; x /= 10; }
while (tp > st) PC(*--tp ^ 48);
}
template <typename Type>
void w_int(Type x) {
if (x < 0) { PC('-'); w_uint(-x); }
else w_uint(x);
}
template <typename Type>
void w_db(Type x) {
double l = floor(abs(x));
string s;
if (x < 0) { PC('-'); x = -x; }
x -= l;
if (!l) PC(48);
while (l) { s.push_back(l - floor(l / 10) * 10); l = floor(l / 10); }
for (auto i = s.rbegin(); i != s.rend(); ++i) PC(*i ^ 48);
PC(46);
for (unsigned long long f = 0; f < h; ++f) {
x *= 10;
PC(floor(x - floor(x / 10) * 10) + 48);
}
}
struct IO {
IO& operator>>(char& x) { do { x = GC(); } while (x == 32 || x == 10 || x == 13); return *this; }
IO& operator>>(string& x) {
char c;
operator>>(c);
x = c;
for (c = GC(); c != 32 && c != 10 && c != 13; c = GC()) x.push_back(c);
x.shrink_to_fit();
return *this;
}
IO& operator>>(short& x) { r_int(x); return *this; }
IO& operator>>(int& x) { r_int(x); return *this; }
IO& operator>>(long& x) { r_int(x); return *this; }
IO& operator>>(long long& x) { r_int(x); return *this; }
IO& operator>>(unsigned short& x) { r_uint(x); return *this; }
IO& operator>>(unsigned int& x) { r_uint(x); return *this; }
IO& operator>>(unsigned long& x) { r_uint(x); return *this; }
IO& operator>>(unsigned long long& x) { r_uint(x); return *this; }
IO& operator>>(float& x) { r_db(x); return *this; }
IO& operator>>(double& x) { r_db(x); return *this; }
IO& operator<<(short x) { w_int(x); return *this; }
IO& operator<<(int x) { w_int(x); return *this; }
IO& operator<<(long x) { w_int(x); return *this; }
IO& operator<<(long long x) { w_int(x); return *this; }
IO& operator<<(unsigned short x) { w_uint(x); return *this; }
IO& operator<<(unsigned int x) { w_uint(x); return *this; }
IO& operator<<(unsigned long x) { w_uint(x); return *this; }
IO& operator<<(unsigned long long x) { w_uint(x); return *this; }
IO& operator<<(char x) { PC(x); return *this; }
IO& operator<<(const string& x) { for (auto& i : x) PC(i); return *this; }
IO& operator<<(float& x) { w_db(x); return *this; }
IO& operator<<(double& x) { w_db(x); return *this; }
void flush() { _flush(); }
void precision(unsigned long long p) { h = p; }
IO() {
#ifdef EFILE
Istream = fopen(EFILE ".in", "r");
Ostream = fopen(EFILE ".out", "w");
#else
#ifdef _LOCAL
Istream = fopen("input.txt", "r");
#endif
#endif
}
~IO() { _flush(); }
} bin;
}
using _IO::bin;
void STRUGGLING(unsigned);
void MIST();
signed main() {
unsigned t = 0, _t = 1;
MIST();
#if _MULTI_TESTS
bin >> _t;
#endif
while (t < _t) STRUGGLING(++t);
return 0;
}
// :/
void STRUGGLING([[maybe_unused]] unsigned TEST_NUMBER) {
tp n, m; bin >> n >> m;
mt19937 rnd(217);
vector<tp> a(n + 1);
vector<vector<tp>> app(6e4);
for (tp i = 1; i <= n; ++i) {
bin >> a[i];
app[a[i]].push_back(i);
}
while (m--) {
bool f = true;
tp l, r, e; bin >> l >> r;
e = r - l + 1;
for (tp _ = 0; _ < 40; ++_) {
tp c = rnd() % e; c = a[c + l];
auto high = upper_bound(app[c].begin(), app[c].end(), r);
auto low = lower_bound(app[c].begin(), app[c].end(), l);
if (high - low > e / 2) { bin << c << '\n'; f = false; break; }
}
if (f) bin << "0\n";
}
}
void MIST() {
}
//*/