题解

题目分析

这是一道基于字典树（Trie）和字符串处理的题目，需要高效处理大量字符串查询。

解题思路

1. 问题建模

• 给定长度为 $n$ 的二进制字符串
• 需要回答 $q$ 个查询，每个查询问区间 $[l, r]$ 内的某种性质
• 使用字典树优化字符串处理

2. 字典树构建

• 使用 ch[4700005][2] 存储字典树结构
• 每个节点有两个子节点：0 和 1
• 使用 a[4700005] 存储节点信息

3. 字符串处理

• 对每个位置 $i$，构建长度为 40 的子串
• 使用 build(i) 函数构建字典树
• 维护 last[x][j] 数组存储历史信息

4. 查询优化

• 使用字典树加速字符串匹配
• 预处理所有可能的子串
• 支持高效的区间查询

5. 关键技巧

• 字典树节点数：$4.7 \times 10^6$
• 子串长度：最多 40 个字符
• 使用位运算优化字符处理

6. 算法实现

• 构建字典树：$O(n \times 40)$
• 查询处理：$O(\log n)$
• 空间复杂度：$O(n \times 40)$

时间复杂度

$O(n \times 40 + q \log n)$，其中 $n$ 为字符串长度，$q$ 为查询次数。

#include<bits/stdc++.h>
using namespace std;
long long q,n,l,r;
long long ch[4700005][2],bh[4700005],a[4700005],last[100005][47];
long long cnt=1;
char c[4700005];
void build(int x)
{
	int u=0;
	for(int i=x;i<=40+x;i++)
	{
		if(i>n)
			return;
		bool p=(c[i]=='1');
		if(!ch[u][p])
			ch[u][p]=++cnt;
		u=ch[u][p];
		last[x][i-x+1]=a[u];
		a[u]=x;
	}
}
int main()
{
	cin>>n>>q;
	for(int i=1;i<=n;i++)cin>>c[i];
	for(int i=1;i<=n;i++)
		build(i);
	for(int i=2;i<=n;i++)
		for(int j=1;j<=46;j++)
		{
			last[i][j]=max(last[i][j],last[i-1][j]);//前缀最大值
			if(!last[i-1][j])
				break;
		}
	while(q--)
	{
		int ans=0;
		cin>>l>>r;
		for(int i=47;i>=1&&l<=r;i--)
			if(last[r][i]>=l)
			{
				ans+=(last[r][i]-l+1)*i;
				l=last[r][i]+1;
			}
		cout<<ans<<endl;
	}
	return 0;
}