回滚莫队求调

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n, q;
ll a[200005];
struct node {
	ll l, r, id;
} b[100005];
ll ha[200005];
ll x[200005];
ll block;
ll id[200005];
ll ans[100005];
ll now;
void Add(ll p) {
	x[p]++;
	now = max(x[p] * ha[p], now);
}
int main() {
	cin.tie(0), cout.tie(0);
	ios::sync_with_stdio(0);
	cin >> n >> q;
	block = sqrt(n);
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		ha[i] = a[i];
		id[i] = (i - 1) / block + 1;
	}
	sort(ha + 1, ha + n + 1);
	int n2 = unique(ha + 1, ha + n + 1) - ha - 1;
	for (int i = 1; i <= n; i++) {
		a[i] = lower_bound(ha + 1, ha + n2 + 1, a[i]) - ha;
	}
	for (int i = 1; i <= q; i++) {
		cin >> b[i].l >> b[i].r;
		b[i].id = i;
		if (b[i].r - b[i].l <= block) {
			for (int j = b[i].l; j <= b[i].r; j++) {
				x[a[j]]++;
			}
			ll nowans = 0;
			for (int j = b[i].l; j <= b[i].r; j++) {
				nowans = max(nowans, x[a[j]] * ha[a[j]]);
				x[a[j]]--;
			}
			ans[i] = nowans;
			b[i].l = n + block;
			b[i].r = n + block;
		}
	}
	sort(b + 1, b + q + 1, [](node X, node Y) {
		if (id[X.l] != id[Y.l])
			return X.l < Y.l;
		return X.r < Y.r;
	});
	int l = 1, r = 0, lstid = 0, backans = 0, backl = 0;
	for (int i = 1; i <= q && b[i].l <= n; i++) {
		if (lstid != id[b[i].l]) {
			lstid = id[b[i].l];
			l = (block) * (lstid) +1;
			r = l - 1;
			now = 0;
			backans = 0;
			memset(x, 0, sizeof x);
		}
		while (r < b[i].r) {
			r++;
			Add(a[r]);
		}
		backans = now;
		backl = l;
		while (l > b[i].l) {
			l--;
			Add(a[l]);
		}
		ans[b[i].id] = now;
		now = backans;
		while (l < backl) {
			x[a[l]]--;
			l++;
		}
	}
	for (int i = 1; i <= q; i++) {
		cout << ans[i] << "\n";
	}
	return 0;
}