自动搬运

查看原文

来自洛谷，原作者为

	chenxi797 壶关条件见主页，私||关我可得2小号回关，私||初三蒟蒻||ENTP||天秤座

搬运于2025-08-24 21:30:20，当前版本为作者最后更新于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;
}