题解：P1787 [入门赛 #22] 非众数 Hard Version 题解

chenxi797 · 2025-07-25 10:08:46 · 题解

P1787 [入门赛 #22] 非众数 Hard Version 题解

题意

定义非众数串：假设其长度为 x，其中每一个数出现的次数都小于等于 \lfloor \frac{x}{2} \rfloor。

现在给出一个序列 s，求 s 的非空子串中非众数串的个数。

思路

直接统计较难，可以用总子串个数 \frac{n \times (n + 1)}{2} 减去满足有一个字母出现的次数大于 \lfloor \frac{x}{2} \rfloor 的子串的个数。

注意到这样的字母是有且仅有一个的，所以用前缀和统计配合树状数组即可

代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 400005;
int c[N],sum[N];
int n,ans;
int lowbit(int x) { return x &= (-x);}
int query(int x)
{
    int ans = 0;
    while (x) ans += c[x],x -= lowbit(x);
    return ans;
}
void up(int x)
{
    for (int i = x;i <= 4 * n + 1;i += lowbit(i))
        c[i]++;
}
signed main()
{
    string s;
    cin >> s;
    n = s.length(),s = " " + s;
    for (int i = 0;i < 26;i++)
    {
        memset(sum,0,sizeof(sum));
        memset(c,0,sizeof(c));
        up(2 * n + 1);
        for (int j = 1;j <= n;j++){
            sum[j] = sum[j - 1] + ((s[j] - 'a')==i);
            ans += query(2 * sum[j] - j - 1 + 2 * n + 1);
            up(2 * sum[j] - j + 2 * n + 1);
        }
    }
    cout << n * (n + 1) / 2 - ans;
    return 0;
}