题解 | #奏绝#
奏绝
https://ac.nowcoder.com/acm/problem/273231
题目链接：E-奏绝_牛客小白月赛93
题目分类：前缀和与差分
思路：由于需要统计区间内端点不同的子区间的长度总和
先设ans[i]:区间[1,i]中的端点不同的子区间的长度总和
考虑如何求解ans[i]
我们遍历一遍1~n，设当前遍历到了第i个字符
若字符i为0，则ans[i]=前面每一个1与这个0的长度总和
考虑如何求解这个
我们发现，前面每一个1与这个0的长度总和 可以转化成 前面1的个数*i的下标-前面每个1所在的下标
所以可以设数组
pre0[i],pre1[i]:前i位数字中0/1数字之和
sum0[i],sum1[i]:前i位数字中0/1数字所在的下标之和
那么答案就是ans[i]=(ans[i-1]+pre1[i-1]*i-sum1[i-1]+MOD)%MOD;
字符i为1同理：ans[i]=(ans[i-1]+pre0[i-1]*i-sum0[i-1]+MOD)%MOD;
然后询问的时候，直接ans[r]-ans[l-1]完事了，吗？并没有
ans[r]-ans[l-1]只是统计了左端点为1，右端点在[l,r]内的答案，还需要减去左端点小于l的部分
考虑如何计算被减的部分
易得，被减的部分就是[l,r]内的1与[1,l-1]内的0，以及[l,r]内的0与[1,l-1]内的1产生的贡献
我们看[l,r]内的1与[1,l-1]内的0，另一个同理
现在的01长度在中间，直接做肯定是不好做的，考虑拆成两个部分，即[1,pos1]-[1,pos0-1]这种形式
对于[1,pos1]，相当于[1,l-1]中0的个数乘上[l,r]中1的下标之和，即pre0[l-1]*(sum1[r]-sum1[l-1])%MOD
对于[1,pos0-1]，相当于[l,r]中1的个数乘上[1,l-1]中0的下标之和，即sum0[l-1]*(pre1[r]-pre1[l-1])%MOD
这样子就行了
代码如下
#define int long long
char s[N];
int pre0[N],pre1[N];
// pre0[i]: 前i个位置中0的个数
// pre1[i]: 前i个位置中1的个数
int sum0[N],sum1[N];
// sum0[i]: 前i个位置中所有0的位置下标之和
// sum1[i]: 前i个位置中所有1的位置下标之和
int ans[N];
// ans[i]: 前i个位置中所有满足条件的子区间（端点不同）的长度和
void InfiniteLight() {
int n,m;
read(n);
read(m);
read(s+1);
Forl(i,1,n){
pre0[i]=pre0[i-1]+(s[i]=='0');
pre1[i]=pre1[i-1]+(s[i]=='1');
sum0[i]=(sum0[i-1]+(s[i]=='0')*i)%MOD;
sum1[i]=(sum1[i-1]+(s[i]=='1')*i)%MOD;
if(s[i]=='0'){
ans[i]=(ans[i-1]+pre1[i-1]*i-sum1[i-1]+MOD)%MOD;
}else{
ans[i]=(ans[i-1]+pre0[i-1]*i-sum0[i-1]+MOD)%MOD;
}
}
Forl(i,1,m){
int l,r;
read(l);
read(r);
int res=(ans[r]-ans[l-1]+MOD)%MOD;
//减去左端点小于l的部分
res=(res-pre0[l-1]*(sum1[r]-sum1[l-1])%MOD-pre1[l-1]*(sum0[r]-sum0[l-1])%MOD+3LL*MOD)%MOD;
res=(res+sum0[l-1]*(pre1[r]-pre1[l-1])%MOD+sum1[l-1]*(pre0[r]-pre0[l-1])%MOD)%MOD;
println(res);
}
return ;
}
