题目链接: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 ; }