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

· · 题解

题解

P1787

传送门专区\texttt:

【Hard Version】P1787 [入门赛 #22] 非众数 Hard Version

【Easy Version】B3967 [语言月赛 202404] 非众数

题目背景

本题是「非众数」的 Hard Version，1 \le n \le 10^5，感谢 @yummy 的贡献。

题目描述

给定一个长度为 n 的字符串 s，保证 s 仅包含小写字母，求 s 的非空子串中非众数串的个数。

定义：非空子串

用 s_i 表示 s 中的第 i 个字符（1 \leq i \leq n）。任取两个整数 i, j（1 \leq i \leq j \leq n），将 s_i, s_{i + 1}, \cdots, s_{j} 截取出来按原序排列作为一个新的字符串，则这个字符串叫做 s 的非空子串。
例如，当 s = \texttt{abcde} 时，\texttt{ab}, \texttt{bcde}, \texttt{c}, \texttt{abcde} 都是 s 的非空子串，而 \texttt{acd}, \texttt{f}, \texttt{ngioasd}, \texttt{" "} 都不是 s 的非空子串。

定义：非众数串

若字符串 a 中出现次数最多的字符出现的次数不超过 \lfloor \frac{|a|}{2} \rfloor，则称字符串 a 为一个非众数串。其中 \lfloor x \rfloor 代表 \leq x 的最大整数，|a| 代表 a 的长度。

输入格式

一行一个字符串，表示 s。

输出格式

一行一个整数，表示答案。

输入输出样例 #1

输入 #1

aabb

输出 #1

2

输入输出样例 #2

输入 #2

fqmdfnc

输出 #2

21

说明/提示

样例 1 解释

其中 \texttt{ab,aabb} 是非众数非空子串。

数据范围

对于 100\% 的数据，1 \le n \le 10^5，字符串由小写字母组成。

思路略解：

为了解决这个问题，我们需要统计给定字符串的所有非空子串中满足非众数条件的子串数目。非众数子串的定义是其出现次数最多的字符的出现次数不超过子串长度的一半。

方法思路

  1. 问题转换：我们将问题转换为统计所有存在主元素（即某个字符出现次数超过子串长度的一半）的子串数目，然后用总子串数目减去这些数目。

  2. 前缀和与树状数组：对于每个字符，我们将字符串转换为一个由+1和-1组成的数组，并计算前缀和。使用树状数组来高效统计满足条件的子数组数目。

  3. 离散化处理：通过偏移量处理前缀和的取值范围，使其适应树状数组的索引范围，从而高效查询和更新。

解决代码

AC Code

#include <bits/stdc++.h>
using namespace std;

const int OFFSET = 100000;  // 1e5的偏移量
const int MAX_VAL = 200002;  // 2e5 + 2

struct FenwickTree {
    vector<int> tree;

    FenwickTree() : tree(MAX_VAL + 1, 0) {}

    void update(int val) {
        val++;  // 树状数组索引从1开始
        while (val <= MAX_VAL) {
            tree[val]++;
            val += val & -val;
        }
    }

    int query(int val) {
        val++;  // 树状数组索引从1开始
        int res = 0;
        while (val > 0) {
            res += tree[val];
            val -= val & -val;
        }
        return res;
    }

    void clear() {
        fill(tree.begin(), tree.end(), 0);
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    string s;
    cin >> s;
    int n = s.size();
    long long total = static_cast<long long>(n) * (n + 1) / 2;
    long long main_count = 0;

    FenwickTree ft;

    for (char c = 'a'; c <= 'z'; ++c) {
        vector<int> a(n);
        for (int i = 0; i < n; ++i) {
            a[i] = (s[i] == c) ? 1 : -1;
        }

        vector<int> prefix_sum(n + 1);
        prefix_sum[0] = 0;
        for (int i = 1; i <= n; ++i) {
            prefix_sum[i] = prefix_sum[i - 1] + a[i - 1];
        }

        ft.clear();
        ft.update(0 + OFFSET);  // 初始前缀和为0，加上偏移量

        long long res_c = 0;
        for (int j = 1; j <= n; ++j) {
            int current = prefix_sum[j];
            int val = current + OFFSET;
            int count = ft.query(val - 1);  // 查询比val小的数目
            res_c += count;
            ft.update(val);
        }

        main_count += res_c;
    }

    long long ans = total - main_count;
    cout << ans << "\n";

    return 0;
}

\text {\green {AC} \color{000000}{Recode}}

上面这个可以点哦 ↑

代码解释

这种方法通过巧妙的问题转换和高效的数据结构应用，将复杂度降低到可接受的范围，适用于大规模输入。

否则就会 ...

欸，不对！放错图了！

这张才是：