题目分类:前缀和与差分
思路:由于需要统计区间内端点不同的子区间的长度总和
先设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 ;
}