自动搬运

查看原文

来自洛谷，原作者为

	Farkas_W 醉后不知天在水，满船清梦压星河。

搬运于2025-08-24 21:52:08，当前版本为作者最后更新于2021-10-10 15:03:28，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

$\quad$我们的模拟赛考了这道题，只会暴力的 30 分，考后看 std 才发现随机数据是怎么用的。(另外其他题解也太长了吧)

$\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}$，满足

$\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，目前最优解。如果有什么疑问就看代码吧。

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;
}