老年退役选手球调板子题。

#include<bits/stdc++.h>
using namespace std;
#define I inline
#define gc getchar
#define pc putchar
const int N = 300010, B = 550;
int n, m, a[N], b[N], in[N], L[N], R[N], id[B][B], cnt[N], sum[N][B];
I int read() {
	int x = 0, f = 1; char ch = gc(); 
	while(ch < '0' || ch > '9') {if(ch == '-') f = -f; ch = gc();}
	while(ch >= '0' && ch <= '9') x = x * 10 + (ch ^ 48), ch = gc();
	return x * f;
}
I void write(int x) {
	if(x < 0) pc('-'), x = -x;
	if(x == 0) {pc('0'); return ;}
	int tot = 0; char s[12];
	while(x) s[tot++] = x % 10 + '0', x /= 10;
	while(tot--) pc(s[tot]);
}
int now, mx;
I void chk(int i, int c) {
	if(c > mx) now = i, mx = c;
	if(c == mx && i < now) now = i;
}
I int ask(int x, int l, int r) {
	return sum[x][r] - sum[x][l - 1];
}
int main() {
	n = read(); int q = n;
	for(int i = 1; i <= n; i++) a[i] = read(), b[i] = a[i];
	sort(b + 1, b + 1 + n);
	int tot = unique(b + 1, b + 1 + n) - b - 1;
	for(int i = 1; i <= n; i++) a[i] = lower_bound(b + 1, b + 1 + tot, a[i]) - b;
	int len = sqrt(n);
	for(int i = 1; i <= n; i++) in[i] = (i + len - 1) / len;
	int blo = in[n];
	for(int i = 1; i <= blo; i++) L[i] = (i - 1) * len + 1, R[i] = min(i * len, n);
	for(int i = 1; i <= blo; i++) {
		for(int j = 1; j <= n; j++) sum[j][i] = sum[j][i - 1];
		for(int j = L[i]; j <= R[i]; j++) sum[a[j]][i]++;
	}
	for(int i = 1; i <= blo; i++) {
		for(int j = i; j <= blo; j++) {
			for(int k = L[j]; k <= R[j]; k++) {
				cnt[a[k]]++;
				if(cnt[a[k]] > cnt[id[i][j]]) id[i][j] = a[k];
				if(cnt[a[k]] == cnt[id[i][j]] && a[k] < id[i][j]) id[i][j] = a[k];
			}
		}
		for(int j = 0; j <= n; j++) cnt[j] = 0;
	}
	while(q--) {
		int l = read(), r = read(); now = mx = 0;
		if(in[l] == in[r]) {
			for(int i = l; i <= r; i++) cnt[a[i]] = 0;
			for(int i = l; i <= r; i++) {
				cnt[a[i]]++;
				chk(a[i], cnt[a[i]]);
			}
			for(int i = l; i <= r; i++) cnt[a[i]] = 0;
			write(b[now]); pc('\n');
		}
		else {
			now = id[in[l] + 1][in[r] - 1]; mx = ask(now, in[l] + 1, in[r] - 1);
			for(int i = l; i <= R[in[l]]; i++) cnt[a[i]] = 0;
			for(int i = L[in[r]]; i <= r; i++) cnt[a[i]] = 0;
			for(int i = l; i <= R[in[l]]; i++) {
				cnt[a[i]]++;
				chk(a[i], cnt[a[i]] + ask(a[i], in[l] + 1, in[r] - 1));
			}
			for(int i = L[in[r]]; i <= r; i++) {
				cnt[a[i]]++;
				chk(a[i], cnt[a[i]] + ask(a[i], in[l] + 1, in[r] - 1));
			}
			write(b[now]); pc('\n');
		}
	}
	return 0;
}