E. Decode

https://codeforces.com/contest/1996/problem/E

题意：给定一个01字符串s，统计区间[l, r]中，[x, y]([l, r]的子区间）中0和1出现次数相等的字符串。

思路：维护一个cnt值，并计算以当前下标j结尾，所有满足条件的起始下标i中，对最后答案的总贡献是多少。一次遍历+map查询即可。

总结：很容易想到如果只是判定满足条件的区间数量，就直接维护一个红黑树来记录cnt值出现的次数即可。 但是题目不仅要求出这个次数，还要求出有多少个区间包含了当前的这个区间。 很容易想到当前下标j结尾后面可以有(n - j)个区间可以包含它，但是对于符合条件的区间，可能不止有一个i，所以这里维护的红黑树不再维护cnt出现的次数，而是维护cnt出现时，当前的cnt左边的区间长度，这样就可以满足计算要求了。
一开始思路错了，只考虑了满足条件的区间中对后面区间的贡献，以及对前面区间的贡献（reverse了string重新计算了一次），但是没考虑对前后区间都有贡献的情况。

void solve(){
    string s;
    cin >> s;

    int n = (int)s.size();

    map<int, MInt> mapp;

    int cnt = 0;
    MInt ans = 0;
    for (int i = 0; i < n; ++i) {
        mapp[cnt] += (i + 1);
        cnt += (s[i] == '1' ? 1 : -1);
        ans += mapp[cnt] * (n - i);
    }

    cout << ans << '\n';
}   

MInt是一个模数字类
https://github.com/yxc-s/programming-template/blob/master/NumberTheory/ModularInteger.cpp