自动搬运

查看原文

来自洛谷，原作者为

	喵仔牛奶 黄昏再美终要黑夜。

搬运于2025-08-24 22:44:52，当前版本为作者最后更新于2024-07-10 20:28:42，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

$\mathcal{O}(n\cdot\lvert\Sigma\rvert)$ 题解，可以加强到 $\lvert\Sigma\rvert=26$ 及以上。

Solution

Part I

我们观察一个子串的合法条件，记 $S$ 为子串 $[l,r]$ 中字符组成的集合，$e_i$ 为 $i$ 的出现次数，从 $S$ 中任选一个数 $x$，可以得到条件为：

$$\forall i\in S,e_i-e_x=0$$

我们记 $s_{i,j}$ 是前 $i$ 个位置中 $j$ 的出现次数，则上述条件变为：

$$\forall i\in S,s_{r,i}-s_{l-1,i}-s_{r,x}+s_{l-1,x}=0 $$$$\forall i\in S,s_{r,i}-s_{r,x}=s_{l-1,i}-s_{l-1,x} $$

也就是说，我们固定 $S,x$，记 $d_{i,j}=s_{i,j}-s_{i,x}$，子串 $[l,r]$ 的合法条件就是：

$$\begin{cases} \forall i\in S,d_{r,i}=d_{l-1,i},\\ \forall i\notin S,s_{r,i}=s_{l-1,i} \end{cases} $$

Part II

我们要枚举的是 $S$，当然不能大力 $2^{\lvert\Sigma\rvert}$ 枚举。我们有结论：

• 固定左端点 $l$，所有右端点 $r$ 产生 $S$ 的种类只有 $\lvert\Sigma\rvert$ 种。固定右端点同理。

我们考虑向右拓展，一种字符之后被加入一次。我们记 $L_i$ 是右端点为 $i$ 向左拓展过程中所有 $S$ 的集合，$R_i$ 是左端点为 $i$ 向右拓展过程中所有 $S$ 的集合。

我们同时枚举端点与集合。枚举左端点与集合 $(l,S)$（$S\in R_l$）、右端点与集合 $(r,T)$（$T\in L_r$）。为了方便，我们将 $x$ 取集合中最小值，即 $x=\min S,x'=\min T$。将 $d,s$ 统一，记 $p_{i,j}=s_{i,j}-\begin{cases}s_{i,x}&j\in S\\0&j\notin S\end{cases}$，$q_{i,j}=s_{i,j}-\begin{cases}s_{i,x'}&j\in T\\0&j\notin T\end{cases}$。可以得出 $[l,r]$ 合法的条件是：

$$\begin{cases} l\leq r,\\ S=T,\\ p_{l-1}=q_r \end{cases} $$

大力枚举是 $\mathcal{O}(n^2\cdot\lvert\Sigma\rvert^2)$ 的，我们发现三个条件除了第一个都是相等，自然分别枚举 $(l,S),(r,T)$ 放进哈希表计数。

考虑到 $l\leq r$，我们枚举 $i=0,1,2,\cdots,n$，先统计以 $i$ 为右端点的答案，即枚举 $S\in L_i$，算出 $p$，答案加上哈希表里 $(S,p)$ 的个数；再枚举 $T\in R_{i-1}$，算出 $q$，将 $(T,q)$ 放入哈希表。

枚举的时候每次往 $S,T$ 里加入一个字符，所以 $p,q$ 与哈希值也是可以维护的。时间复杂度 $\mathcal{O}(n\cdot\lvert\Sigma\rvert)$。

细节见代码，有注释。

Code

#include <bits/stdc++.h>
#define REP(i, l, r) for (int i = (l); i <= (r); ++ i)
#define DEP(i, r, l) for (int i = (r); i >= (l); -- i)
#define fi first
#define se second
#define pb emplace_back
#define mems(x, v) memset((x), (v), sizeof(x))
using namespace std;
namespace Milkcat {
	typedef long long LL;
	typedef unsigned long long ULL;
	typedef pair<LL, LL> pii;
	const int N = 1e6 + 5, B = 1e7 + 7;
	
	LL n, m, rs, a[N], ct[N][26]; string st;
	ULL pw[N]; vector<int> L[N], R[N];
	unordered_map<ULL, int> S;
	
	void ins(vector<int>& s, int x) {
		int t = -1;
		for (int i = 0; i < s.size(); i ++)
			if (s[i] == x) t = i;
		if (t != -1) s.erase(s.begin() + t);
		s.insert(s.begin(), x);
	} // s 中没有 x 则将 x 加到最前，有则将里面 x 的位置放到最前。
	
	int main() {
		cin >> st, n = st.size();
		REP(i, 1, n) {
			a[i] = st[i - 1] - 'a', m = max(m, a[i] + 1);
			REP(j, 0, 25) ct[i][j] = ct[i - 1][j] + (a[i] == j); // ct 是题解中的 s
		}
		REP(i, 1, n) L[i] = L[i - 1], ins(L[i], a[i]);
		DEP(i, n, 1) R[i] = R[i + 1], ins(R[i], a[i]);
		// 处理出 L,R
		pw[0] = 1;
		REP(i, 1, n + m) pw[i] = pw[i - 1] * B;
		
		REP(i, 0, n) {
			if (i > 0) {
				ULL v = 0, w = 0, s = 0, c = 1e9; // v 是 p 的哈希值，w 是 S 的哈希值，s 辅助求哈希值，c 是 x（最小值）
				DEP(j, m - 1, 0) v = v * B + ct[i][j];
				for (int x : L[i]) {
					if (x < c) v += s * (c < m ? ct[i][c] - ct[i][x] : 0), c = x;  // 最小值改变，要改变之前 -ct[i][c] 的部分（即 s）
					v -= ct[i][c] * pw[x], s += pw[x], w |= 1 << x; // 加入一个数
					rs += S[v + w * pw[m]]; // 统计答案
				}
			}
			ULL v = 0, w = 0, s = 0, c = 1e9;
			DEP(j, m - 1, 0) v = v * B + ct[i][j];
			for (int x : R[i + 1]) {
				if (x < c) v += s * (c < m ? ct[i][c] - ct[i][x] : 0), c = x;
				v -= ct[i][c] * pw[x], s += pw[x], w |= 1 << x; // 和前面一模一样
				S[v + w * pw[m]] ++;
			}
		}
		cout << rs << '\n';
		return 0;
	}
}
int main() {
//	freopen("c.in", "r", stdin);
//	freopen("c.out", "w", stdout);
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	int T = 1;
	while (T --) Milkcat::main();
	return 0;
}