C114 回滚莫队 歴史の研究

视频链接：C114 回滚莫队 歴史の研究_哔哩哔哩_bilibili

Luogu AT_joisc2014_c 歴史の研究

// 回滚莫队 O(n^(3/2))
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;

#define LL long long
const int N=1000005;
int n,m,B,block[N];
LL a[N],b[N];
LL res,last,ans[N],cnt[N],c[N];
struct Q{
  int l,r,id;
  bool operator<(Q &b){
    if(block[l]!=block[b.l])return l<b.l;
    return r<b.r;
  }
}q[N];

void add(int x){ //加上一个数的贡献
  ++cnt[x];
  res=max(res,cnt[x]*b[x]);
}
LL calc(int l,int r){ //暴力计算块内
  LL mx=0;
  for(int i=l;i<=r;++i)c[a[i]]=0;
  for(int i=l;i<=r;++i){
    ++c[a[i]];
    mx=max(mx,c[a[i]]*b[a[i]]);
  }
  return mx;
}
int main(){
  scanf("%d%d",&n,&m); B=sqrt(n); //块长
  for(int i=1;i<=n;++i)
    scanf("%lld",a+i),b[i]=a[i],
    block[i]=(i-1)/B+1; //i在哪个块
  int num=block[n];     //块数
  sort(b+1,b+n+1);
  for(int i=1;i<=n;++i) //离散化a
    a[i]=lower_bound(b+1,b+n+1,a[i])-b;
  for(int i=1,l,r;i<=m;++i)
    scanf("%d%d",&l,&r),q[i]={l,r,i};
  sort(q+1,q+m+1);
  
  for(int i=1,x=1;i<=num;++i){  //第i块
    res=last=0;
    for(int j=1;j<=n;++j)cnt[j]=0; //清空
    int R=min(B*i,n),l=R+1,r=R;
    for(;block[q[x].l]==i;++x){ //第i块的查询x
      if(block[q[x].l]==block[q[x].r]){ //块内
        ans[q[x].id]=calc(q[x].l,q[x].r);
        continue;
      }
      while(r<q[x].r)add(a[++r]); //右扩展
      last=res;         //结果存为last
      while(l>q[x].l)add(a[--l]); //左扩展
      ans[q[x].id]=res; //结果存入答案
      while(l<=R) --cnt[a[l++]];  //回滚l
      res=last;         //回滚结果
    }
  }
  for(int i=1;i<=m;++i)printf("%lld\n",ans[i]);
}