题解 AT1219 【歴史の研究】

· · 题解

分块

比回滚莫队简单，但时间复杂度为 O(n\sqrt{n}logn)，而回滚莫队是 O(n\sqrt{n}) 的。

可以预处理 i 为每块开头的 f_{ij} 和 cnt_{ij}。

对于每次询问的 x,y ，只需要求出每个 a_i 在这个区间中的重要度，然后取最大值即可。

重要度就是 a_i×a_i在 [x,y] 中出现的次数。

如果 x 是块的开头，就可以直接用 cnt，否则就把 [x,y] 分成3段，

$2.$ $x$ 到 $b_x$的末尾。 $3.$ $b_x+1$ 到 $b_y-1$。 将 $1$ 和 $2$ 的和存进 $num_{a_i}$，$a_i$ 出现的个数就是 $cnt_{b_x+1,a_i}-cnt_{b_y,a_i}+num_{a_i}

一个小容斥。

代码：

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>

using namespace std;

const int N=1e5+10;
const int B=333;
typedef long long ll;

int n,q,Block,a[N],b[N];
ll f[B][N],ans,cpy[N],cnt[B][N],stk[N],num[N];

int main()
{
    scanf("%d%d",&n,&q);
    Block=sqrt(n);      //块的大小 
    for(int i=1; i<=n; i++)
        scanf("%d",&a[i]),b[i]=(i-1)/Block+1,cpy[i]=a[i];
    sort(cpy+1,cpy+1+n);                //排序 
    int u=unique(cpy+1,cpy+1+n)-cpy-1;  //去重 
    for(int i=1; i<=n; i++) a[i]=lower_bound(cpy+1,cpy+1+u,a[i])-cpy;
    for(int i=1; i<=b[n]; i++)
    {
        ll now=0;
        //预处理i为每块的开头的情况 
        for(int j=lower_bound(b+1,b+1+n,i)-b; j<=n; j++)
        {
            cnt[i][a[j]]++;
            now=max(now,cnt[i][a[j]]*cpy[a[j]]);
            f[i][j]=now;
        }
    }
    while(q--)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        ans=f[b[x]+1][y];
        int top=0,tmp=lower_bound(b+1,b+1+n,b[y])-b;
        //y所在块的开头到y 
        for(int i=tmp; i<=y; i++)
            num[a[i]]++,stk[++top]=a[i];
        //x到x所在块的末尾 
        tmp=lower_bound(b+1,b+1+n,b[x]+1)-b;
        for(int i=x; i<tmp; i++)
        {
            num[a[i]]++;
            stk[++top]=a[i];
            ans=max(ans,(cnt[b[x]+1][a[i]]-cnt[b[y]][a[i]]+num[a[i]])*cpy[a[i]]);
        }
        //用栈记录下出现了哪些种类的事件，最后要清空 
        for(int i=1; i<=top; i++) num[stk[i]]=0;
        printf("%lld\n",ans);
    }
    return 0;
}