题解：B4153 [厦门小学生 C++ 2022] 序列问题

· · 题解

题意已经很简洁了不再赘述。

思路：

首先 n \le 10^7，暴力是肯定过不了的。

考虑前缀和优化快速计算子串数量。因为子串 1 的数量要比 0 多，所以计算前缀和时把 1 看做 1 计算，把 0 看做 -1 计算。那么判断一个区间是否满足要求只需要计算 num_r - num_{l-1} 是否大于 0，再转化一下就是满足 num_r \gt num_{l-1} 即可。

于是就可以记录出在此之前计算出的前缀和比当前的前缀和小的数量就行了。一开始用树状数组维护，但是发现时间复杂度还是有点高。

后来找了几个样例模拟发现，不需要把所有的比当前小的数都维护，可以一个一个传递下去。

设 num 为前缀和，ans 为比当前数小的数量，res 为最终答案。

比如当 s_i 为 1 时，前缀和就为 num+1，比它小的就是 num，ans 需要加上 num 的数量；否则，前缀和就为 num-1，num-1 就不满足条件，ans 需要减去 num-1 的数量。

然后就可以用一个数组记录 num 的数量，不用 map 是因为 map 太慢。因为 num 可能会一直减，为了保证数组下标为非负数，就提前加上 n。

代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e7+5;
int n,res,num,ans;
char s[N];
int mp[N*2];
signed main(){
    scanf("%lld",&n);
    scanf("%s",s+1);
    mp[n]=1;
    for(int i=1;i<=n;i++){
        ans+=s[i]=='1'?mp[n+num]:-mp[n+num-1];
        num+=s[i]=='1'?1:-1;
        mp[n+num]++,res+=ans;
    }printf("%lld",res);
    return 0;
}