rt，以上时间复杂度不区分 $n,m,c$。

可以通过神奇预处理，用分块做到 $O(n\sqrt{n})$。

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define il inline
#define N 300005
il ll rd(){
	ll s = 0, w = 1;
	char ch = getchar();
	for (;ch < '0' || ch > '9'; ch = getchar()) if (ch == '-') w = -1;
	for (;ch >= '0' && ch <= '9'; ch = getchar()) s = ((s << 1) + (s << 3) + ch - '0');
	return s * w;
}
ll n = rd(), c = rd(), a[N], m, sqn, l, r, col[N], nl[605], nr[605], s[605][10005], p[605][605], t[N];
int main(){
	sqn = 500;
	for (int i = 1; i <= n; i++) a[i] = rd(), col[i] = (i + sqn - 1) / sqn;
	for (int i = 1; i <= col[n]; i++) nl[i] = nr[i - 1] + 1, nr[i] = min(i * sqn, n);
	for (int i = 1; i <= col[n]; i++){
		for (int j = 1; j <= c; j++) s[i][j] = s[i - 1][j];
		for (int j = nl[i]; j <= nr[i]; j++) s[i][a[j]]++;
	}for (int i = 1; i <= col[n]; i++){
		ll maxn = a[nl[i]];
		for (int j = nl[i], k = i; j <= n; j++){
			t[a[j]]++;
			if (t[a[j]] > t[maxn]) maxn = a[j];
			if (j == nr[k]) p[i][k] = maxn, k++;
		}for (int j = 1; j <= c; j++) t[j] = 0;
	}for (int m = rd(); m--;){
		l = rd(), r = rd();
		if (col[l] == col[r]){
			ll maxn = a[l];
			for (int i = l; i <= r; i++){
				t[a[i]]++;
				if (t[a[i]] > t[maxn]) maxn = a[i];
			}if (t[maxn] > (r - l + 1) / 2.0) printf ("yes %lld\n", maxn);
			else puts("no");
			for (int i = l; i <= r; i++) t[a[i]] = 0;
			continue;
		}ll maxn = p[col[l] + 1][col[r] - 1];
		for (int i = l; i <= nr[col[l]]; i++){
			t[a[i]]++;
			if (t[a[i]] + s[col[r] - 1][a[i]] - s[col[l]][a[i]] > t[maxn] + s[col[r] - 1][maxn] - s[col[l]][maxn])
				maxn = a[i];
		}for (int i = nl[col[r]]; i <= r; i++){
			t[a[i]]++;
			if (t[a[i]] + s[col[r] - 1][a[i]] - s[col[l]][a[i]] > t[maxn] + s[col[r] - 1][maxn] - s[col[l]][maxn])
				maxn = a[i];
		}if (t[maxn] + s[col[r] - 1][maxn] - s[col[l]][maxn] > (r - l + 1) / 2.0) printf ("yes %lld\n", maxn);
		else puts("no");
		for (int i = l; i <= nr[col[l]]; i++) t[a[i]] = 0;
		for (int i = nl[col[r]]; i <= r; i++) t[a[i]] = 0;
	}
	return 0;
}