看到出现次数自然地考虑莫队。
但是发现如果需要删除并动态维护答案的话，则要用一个堆来维护答案，增加了一个\(log\)。但是加入操作却没有这个\(log\)，所以我们考虑避免删除操作。
分块，设\(l_i,r_i\)表示第\(i\)个块的左右端点，设\(f_{i,j}\)表示区间\([l_i,r_j]\)的答案，可以枚举\(i\)然后枚举\(j\)做到\(O(n\sqrt{n})\)；
接下来将询问离线，对于每一组询问如果左右端点距离\(\leq 2\sqrt{n}\)则暴力计算答案，否则考虑其覆盖的整块\([p,q]\)，则通过莫队将\([l_p,r_q]\)内所有数的出现次数统计下来，然后暴力将零散块的贡献进入出现次数数组并更新当前答案，最后把出现次数数组还原即可。复杂度\(O(n\sqrt{n})\)。
#includeusing namespace std;int read(){ int a = 0; char c = getchar(); bool f = 0; while(!isdigit(c)){f = c == '-'; c = getchar();} while(isdigit(c)){ a = a * 10 + c - 48; c = getchar(); } return f ? -a : a;}const int _ = 1e5 + 7 , S = sqrt(_) , T = _ / S + 10;long long mx[T][T] , ans[_]; int arr[_] , tmp[_] , lsh[_] , N , Q , num;struct query{ int l , r , id , tL , tR; query(int _l , int _r , int _id){ l = _l; r = _r; id = _id; tL = (l / S + 1) * S; tR = (r / S) * S - 1; } friend bool operator <(query A , query B){ return A.tL < B.tL || A.tL == B.tL && A.tR < B.tR; }}; vector < query > qry;void add(int x){++tmp[arr[x]];} void del(int x){--tmp[arr[x]];}signed main(){#ifndef ONLINE_JUDGE freopen("in","r",stdin); freopen("out","w",stdout);#endif N = read(); Q = read(); for(int i = 0 ; i < N ; ++i) arr[i] = lsh[i] = read(); sort(lsh , lsh + N); num = unique(lsh , lsh + N) - lsh - 1; for(int i = 0 ; i < N ; ++i) arr[i] = lower_bound(lsh , lsh + num + 1 , arr[i]) - lsh; for(int i = 0 ; i < N ; i += S){ long long now = 0; for(int j = i ; j < N ; ++j){ now = max(now , 1ll * ++tmp[arr[j]] * lsh[arr[j]]); if(j % S == S - 1 || j + 1 == N) mx[i / S][j / S] = now; } memset(tmp , 0 , sizeof(tmp)); } for(int i = 1 ; i <= Q ; ++i){ int p = read() - 1 , q = read() - 1; long long now = 0; if(q - p <= 2 * S){ for(int k = p ; k <= q ; ++k) now = max(now , 1ll * ++tmp[arr[k]] * lsh[arr[k]]); for(int k = p ; k <= q ; ++k) tmp[arr[k]] = 0; ans[i] = now; } else qry.push_back(query(p , q , i)); } sort(qry.begin() , qry.end()); int L = 0 , R = -1; for(auto t : qry){ while(R < t.tR) add(++R); while(L > t.tL) add(--L); while(R > t.tR) del(R--); while(L < t.tL) del(L++); long long now = mx[L / S][R / S]; for(int i = L - 1 ; i >= t.l ; --i) now = max(now , 1ll * ++tmp[arr[i]] * lsh[arr[i]]); for(int i = R + 1 ; i <= t.r ; ++i) now = max(now , 1ll * ++tmp[arr[i]] * lsh[arr[i]]); ans[t.id] = now; for(int i = t.l ; i < L ; ++i) --tmp[arr[i]]; for(int i = t.r ; i > R ; --i) --tmp[arr[i]]; } for(int i = 1 ; i <= Q ; ++i) printf("%lld\n" , ans[i]); return 0;}