题目：
套路：可以大力预处理，如果求区间加权众数，可以预处理i~j块(或 j 位置)的最大值，为了暴力再预处理i~j块每个数出现次数；这个i~j可以记录成从第i块开始的后缀，这样空间还是n*w。
如果不无脑开long long可以快18s。
#include#include #include #include #include #define ll long longusing namespace std;const int N=1e5+5;int n,q,base,bh[N],sta[N],top,a[N],c[N],cnt[320][N],nm[N];ll f[320][N];int main(){ scanf("%d%d",&n,&q);base=sqrt(n); for(int i=1;i<=n;i++) { scanf("%lld",&a[i]);c[i]=a[i]; bh[i]=(i-1)/base+1; } sort(c+1,c+n+1);int tot=unique(c+1,c+n+1)-c-1; for(int i=1;i<=n;i++)a[i]=lower_bound(c+1,c+tot+1,a[i])-c; for(int i=1;i<=bh[n];i++) { ll tmp=0; for(int j=(i-1)*base+1;j<=n;j++)//i,not bh[i] cnt[i][a[j]]++,tmp=max(tmp,(ll)cnt[i][a[j]]*c[a[j]]),f[i][j]=tmp;//这里把j表示成具体位置也行(好?) //c[a[j]] //之所以用tmp，是为了把之前的值曾达到的最大值也算在自己里 } int x,y; while(q--) { scanf("%d%d",&x,&y); ll ans=f[bh[x]+1][y]; for(int i=(bh[y]-1)*base+1;i<=y;i++) nm[a[i]]++,sta[++top]=a[i]; for(int i=x;i<=bh[x]*base&&i<=n;i++) nm[a[i]]++,sta[++top]=a[i],ans=max(ans,(ll)(cnt[bh[x]+1][a[i]]-cnt[bh[y]][a[i]]+nm[a[i]])*c[a[i]]); printf("%lld\n",ans); for(int i=1;i<=top;i++)nm[sta[i]]=0;top=0; } return 0;}