题解：CF1660F2 Promising String (hard version)

xiaozekai11 · 2026-11-10 20:00:51 · 题解

题意简述

定义一次“操作”为将两个 \texttt{-} 变成一个 \texttt{+}。如果一个字符串经过若干次操作，其 \texttt{+} 与 \texttt{-} 的数量相同，就符合条件。问一个字符串有多少子串符合条件。

思路

设 x 为 \texttt{+} 的数量，y 为 \texttt{-} 的数量。容易发现，一个子串的 x 大于 y，那么它一定不符合条件。另外，可以将 \texttt{+} 视作 2 个 \texttt{-}，如果一个子串的 2 \times x + y 没法整除于 3，那它一定不符合条件。否则则一定满足。

那么，问题就转化为了求有多少个子串，y 大于 x 且 (2 \times x + y) \bmod 3 = 0。

实现

将 \texttt{+} 视作 -1（模 3 意义下为 +2），将 \texttt{-} 视作 1，维护前缀和数组 s。那么对于每个 i，答案为满足 s_j \le s_i 且 s_j \bmod 3 = s_i \bmod 3 的 j 的数量。可以考虑开三个树状数组，分别维护 s_i \bmod 3 = 0, 1, 2 的三种情况。

参考代码

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
ll T,n,d[210000],D=200001;
struct tree{
    ll c[410000];
    ll lowbit(ll x){return x&-x;}
    void add(ll i,ll x){
        for(;i<=D+n;i+=lowbit(i))c[i]+=x;
    }
    ll sum(ll i){
        ll ans=0;
        for(;i;i-=lowbit(i))ans+=c[i];
        return ans;
    }
}c[3];
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>T;
    while(T--){
        cin>>n;
        d[0]=D;
        ll ans=0;
        c[0].add(D,1);
        for(int i=1;i<=n;i++){
            char ch;
            cin>>ch;
            if(ch=='+')d[i]=d[i-1]-1;
            else d[i]=d[i-1]+1;
            ll x=d[i]%3;
            ans+=c[x].sum(d[i]);
            c[x].add(d[i],1);
        }
        for(int i=-n;i<=n;i++)c[0].c[i+D]=c[1].c[i+D]=c[2].c[i+D]=0;
        cout<<ans<<'\n';
    }
    return 0;
}