Description：

求区间加权众数。

$1\le N \le 10^5$

Solution：

分块，先离散化，记 $cnt[i][j]$ 表示从第 $i$ 个块的开头开始到结尾数字 $j$ 的个数， $f[i][j]$ 表示从第 $i$ 个块的开头开始到位置 $j$ 加权众数，这样对于每次询问时只用查询 $[l,R[belong[l]]]$ 之间的数能否成为加权众数，开一个桶记录即可。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<stack>

#include<cstring>

using namespace std;

#define MAXN 100050

int n,q;

int siz,tot,L[MAXN],R[MAXN],belong[MAXN];

int a[MAXN],b[MAXN],s[MAXN],cur = 0;;

int cnt[333][MAXN],num[MAXN];

typedef long long ll;

ll f[333][MAXN];

bool cmp(int x,int y){return a[x] < a[y];}

stack<int> st;

int main()

{

    scanf("%d%d",&n,&q);

    tot = siz = sqrt(n);

    for(int i = 1;i <= tot;++i)

    {

        L[i] = (i - 1) * siz + 1;R[i] = i * siz;

        for(int k = L[i];k <= R[i];++k)

            belong[k] = i;

    }

    if(siz * siz < n)

    {

        ++tot;L[tot] = R[tot - 1] + 1;R[tot] = n;

        for(int k = L[tot];k <= R[tot];++k)

            belong[k] = tot;

    }

    for(int i = 1;i <= n;++i)

    {

        scanf("%d",&a[i]);

        b[i] = i;

    }

    sort(b + 1,b + 1 + n,cmp);

    for(int i = 1;i <= n;++i)

    {

        if(a[b[i]] == a[b[i - 1]])s[b[i]] = cur;

        else s[b[i]] = ++cur;

    }

    for(int i = 1;i <= tot;++i)

    {

        ll now = 0;

        for(int j = L[i];j <= n;++j)

        {

            cnt[i][s[j]]++;

            now = max(now,(ll)cnt[i][s[j]] * a[j]);

            f[i][j] = now;

        }

    }

    int l,r;

    ll ans;

    for(int i = 1;i <= q;++i)

    {

        scanf("%d%d",&l,&r);

        ans = 0;

        if(belong[l] == belong[r])

        {

            for(int j = l;j <= r;++j)

            {

                num[s[j]]++;st.push(s[j]);

                ans = max(ans,(ll)num[s[j]] * a[j]);

            }

            printf("%lld\n",ans);

            while(!st.empty())

            {

                num[st.top()]--;

                st.pop();

            }

            continue;

        }

        ans = f[belong[l] + 1][r];

        for(int j = L[belong[r]];j <= r;++j)

        {

            num[s[j]]++;

            st.push(s[j]);

        }

        for(int j = l;j <= R[belong[l]];++j)

        {

            num[s[j]]++;

            st.push(s[j]);

            ans = max(ans,(ll)(num[s[j]] + cnt[belong[l] + 1][s[j]] - cnt[belong[r]][s[j]]) * a[j]);

        }

        printf("%lld\n",ans);

        while(!st.empty())

        {

            num[st.top()]--;

            st.pop();

        }

    }

    return 0;

}