RT.另外回滚莫队是不能奇偶排序吗qwq

#include <cstdio>
#include <cmath>
#include <algorithm>

#define N 100010
#define ll long long
using namespace std;

ll n,m,a[N],b[N],c[N],idx;
ll len,block,belong[N],L[N],R[N],cnt[N],cnt_bur[N];
ll ans[N];
struct Query
{
	ll l,r,id;
}q[N];

void build()
{
	len = sqrt(n);
	block = n / len;
	if(n % len)
		block++;
	for(ll i = 1;i <= n;i++)
		belong[i] = (i - 1) / len + 1;
	for(ll i = 1;i <= block;i++)
	{
		L[i] = (i - 1) * len + 1;
		R[i] = i * len;
	}
	R[block] = n;
}

bool cmp(Query x,Query y)
{
	return belong[x.l] ^ belong[x.l] ? belong[x.l] < belong[y.l] : x.r < y.r;
}

void insert(ll x,ll &Mx)
{
	cnt[c[x]]++;
	Mx = max(Mx,cnt[c[x]] * a[x]);
}

void resume(ll x)
{
	cnt[c[x]]--;
}

int main()
{
	scanf("%lld%lld",&n,&m);
	for(ll i = 1;i <= n;i++)
	{
		scanf("%lld",&a[i]);
		b[++idx] = a[i];
	}
	sort(b + 1,b + 1 + idx);
	idx = unique(b + 1,b + 1 + idx) - (b + 1);
	for(ll i = 1;i <= n;i++)
		c[i] = lower_bound(b + 1,b + 1 + idx,a[i]) - b;
	for(ll i = 1;i <= m;i++)
	{
		scanf("%lld%lld",&q[i].l,&q[i].r);
		q[i].id = i;
	}
	build();
	sort(q + 1,q + m + 1,cmp);
	ll l = 1,r = 0,last = -1,Max;
	for(ll i = 1;i <= m;i++)
	{
		ll ql = q[i].l,qr = q[i].r;
		if(belong[ql] == belong[qr])
		{
			ll res = 0;
			for(ll j = ql;j <= qr;j++)
				cnt_bur[c[j]]++;
			for(ll j = ql;j <= qr;j++)
				res = max(res,cnt_bur[c[j]] * a[j]);
			for(ll j = ql;j <= qr;j++)
				cnt_bur[c[j]]--;
			ans[q[i].id] = res;
			continue;
		}
		if(last ^ belong[ql])
		{
			while(r > R[belong[ql]])
				resume(r--);
			while(l < R[belong[ql]] + 1)
				resume(l++);
			Max = 0,last = belong[ql];
		}
		while(r < qr)
			insert(++r,Max);
		ll res = Max,l_ = l;
		while(l_ > ql)
			insert(--l_,res);
		while(l_ < l)
			resume(l_++);
		ans[q[i].id] = res;
	}
	for(ll i = 1;i <= m;i++)
		printf("%lld\n",ans[i]);
	return 0;
}