题解 P3732 [HAOI2017]供给侧改革
Farkas_W
·
·
题解
\texttt{前言}
$$\texttt{思路}$$
$\quad$考虑 trie 树，因为是随机数据，显然两段长为 $L$ 的字符串完全相同的概率是 $2^L$，所以取的要尽量大且不会爆空间。我们对于每一个位置，只存其后长为 $45$ 的字符串即可(长度取 $30$ 只可以得到 $70$ 分)，暴力将每一个位置存入时，$last$ 数组记录下最近到达这个位置的 $id$ ，$a$ 数组记录上一个到达这个位置的字符串编号，每次更新 $a$ 数组。
$\quad$设以第 $i$ 个位置开始(结束位置为 $n$) 的字符串为字符串 $i$，建立 trie树后，$last_{i,j}$ 表示与字符串 $i$ 前 $j$ 位完全相同的最近的字符串编号 (这里的最近指的是小于 $i$ 的且最靠近 $i$ 的编号)。
$\quad$接着对 $last$ 数组做一个前缀最大值，$last_{i,j}$ 表示从字符串 $1$ 到字符串 $i$ 中，最大的**一对**长为 $j$ 的前缀相同的字符串编号中较小的。假如 $t=last_{i,j}$，满足
$$data_{k,i}=j(1\leq k\leq t)$$
$\quad$所以对于一个询问 $L,R$，假如 $t=last_{R,j}(t\geq L)$，显然对于 $data_{i,R}(i\in [L,t])=j$，这样区间 $[L,t]$ 的答案就统计好了，接着继续统计询问 $[t+1,R]$ 即可，可以令 $L=t+1$，就这样一段区间一段区间的向后跳。
$\quad$时间复杂度为 $O(45(n^2+Q))$ ，开 $O_2$ 后跑了 207ms，目前最优解。如果有什么疑问就看代码吧。
```cpp
il int max(int x,int y){return x>=y?x:y;}
const int N=5e5+5;
int n,m,a[N*47],ch[N*47][2],cnt,last[N][48];
char c[N];
il void insert(int id)
{
int u=0;
for(re i=id;i<=id+46;i++)//只更新长度47
{
if(i>n)return;bool p=(c[i]=='1');
if(!ch[u][p])ch[u][p]=++cnt;
u=ch[u][p];last[id][i-id+1]=a[u];
a[u]=id;//更新
}
}
signed main()
{
cin>>n>>m>>c+1;
for(re i=1;i<=n;i++)insert(i);
for(re i=2;i<=n;i++)
for(re j=1;j<=47;j++)
{
last[i][j]=max(last[i][j],last[i-1][j]);//前缀最大值
if(!last[i-1][j])break;//表示前面没有前j位相同的字符串
}
while(m--){
int l,r,ans=0;cin>>l>>r;
for(re i=47;i&&l<=r;i--)
if(last[r][i]>=l){ //有符合区间的字符串
ans+=(last[r][i]-l+1)*i;//统计答案
l=last[r][i]+1;
}
cout<<ans<<'\n';
}
return 0;
}
```