歴史の研究(回滚莫队)
题意：
一个数的重要度为数值*出现次数，每次询问一个区间内的最重要度
思路：
- 按左端点块编号排序，再按右端点排序
- 对于左右端点在同一块内的询问，暴力询问 $ qB $
- 对于不在同一块内的区间询问，固定当前右指针为块的右边，因为块内区间右端点升序，因此右指针单调移动，最多为 $ n $ 次，总次数为 $ \frac{n^2}{B} $ 次
- 然后暴力移动左端点，每个块最多为 $ B $ 次，一共 $ n $ 次
- B取 $ \sqrt \frac{n^2}{q} $
cpp
struct Node{
int id,l,r;
};
int w[M];
int be[M],L[M],R[M],tot,block;
bool cmp(Node x,Node y){
return (be[x.l]^be[y.l])?be[x.l]<be[y.l]:x.r<y.r;
}
void solve(){
int n,m;
cin>>n>>m;
vector<int> nums;
for(int i=1;i<=n;i++)cin>>w[i],nums.push_back(w[i]);
sort(nums.begin(),nums.end());
nums.erase(unique(nums.begin(),nums.end()),nums.end());
for(int i=1;i<=n;i++)w[i]=lower_bound(nums.begin(),nums.end(),w[i])-nums.begin();
vector<int> cnt(nums.size());
auto add=[&](int x,int &res){
cnt[x]++;
res=max(res,cnt[x]*nums[x]);
};
vector<int> ans(m+1);
vector<Node> q(m+1);
for(int i=1;i<=m;i++){
cin>>q[i].l>>q[i].r;
q[i].id=i;
}
block=sqrt(1.0*n*n/m),tot=(n+block-1)/block;
for(int i=1;i<=tot;i++){
L[i]=(i-1)*block+1,R[i]=min(i*block,n);
for(int j=L[i];j<=R[i];j++)be[j]=i;
}
sort(q.begin()+1,q.end(),cmp);
for(int i=1,j;i<=m;i++){
j=i;
int right=R[be[q[i].l]];
while(j+1<=m&&be[q[i].l]==be[q[j+1].l])j++;
while(i<=j&&q[i].r<=right){
//左右端点在同一块
auto [id,ql,qr]=q[i++];
int res=0;
for(int k=ql;k<=qr;k++)add(w[k],res);
ans[id]=res;
for(int k=ql;k<=qr;k++)cnt[w[k]]--;//复原
}
int l=right+1,r=right;
int res=0;
while(i<=j){
auto [id,ql,qr]=q[i++];
while(r<qr)add(w[++r],res);
int backup=res;
while(l>ql)add(w[--l],res);
ans[id]=res;
res=backup;
while(l<right+1)cnt[w[l++]]--;
}
while(r>right)cnt[w[r--]]--;
i=j;
}
for(int i=1;i<=m;i++)cout<<ans[i]<<"\n";
}