串串题

Nostopathy · 2025-09-20 13:07:44 · 题解

今天下午是 S 第一轮，听说考前发题解能增加 RP，于是就有了这篇题解。

题意

定义非众数串为：串中每一个字母出现次数不超过长度的一半。

求给定字符串中非众数串的数量。

分析

直接求较复杂，考虑正难则反，用总子串数 \frac{n(n+1)}{2} 减去众数串数量。

而一个子串中出现次数超过长度一半的字母有且仅有一个。

则可以枚举每个字母，用前缀和统计出现次数，结合树状数组查询次数，累加答案。

代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define pb push_back
const int N = 4e5 + 5;
int lb(int x) {
    return x&(-x);
}
int n, sm[N], p[N];
void c(int x) { //更新
    for(int i=x; i<=n*4+1; i+=lb(i))
        ++sm[i];
}
int q(int x) { //查询
    int s=0;
    for(int i=x; i; i-=lb(i))
        s+=sm[i];
    return s;
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    string s;
    cin>>s;
    n=s.size();
    s=" "+s;
    int ans=0;
    for(int i=0; i<=25; ++i) {
        memset(sm, 0, sizeof sm);
        memset(p, 0, sizeof p);
        c(n*2+1);
        for(int j=1; j<=n; ++j) {
            p[j]=p[j-1]+(s[j]-'a'==i);
            ans+=q(2*n+1+2*p[j]-j-1);
            c(2*n+1+2*p[j]-j);
        }
    }
    ans=n*(n+1)/2-ans;
    cout<<ans;
    return 0;
}

祝大家 CSP RP++！