自动搬运

查看原文

来自洛谷，原作者为

	DengDuck 澳門現役 OIer，萌萌未花日奈雙推人一枚

搬运于2025-08-24 21:44:52，当前版本为作者最后更新于2023-07-29 02:14:55，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

前言

现在是 $2023$ 年 $7$ 月 $29$ 日凌晨 $1$ 点 $47$ 分，我听着我歌单的歌，进入了精神极其不正常的状态（正经人谁在凌晨边听摇滚边写题啊）。

所以我会胡言几句，大家请选择性忽视。

这道题是我们欢乐赛搬的，考场上用朴素的 $O(nm^2)$ 双指针水出了 $89$ 分的佳绩。

考试之后因为没有暴切十分气愤啊！所以研读了一手第一篇题解，写出了这个没什么区别但是有大区别的高级重置优秀版。

题目分析

第一次转换

括号序列的合法可以运用一个转换来判断。

把左括号变成 $1$，右括号变成 $-1$，然后求前缀和 $sum$，合法的序列 $[l,r]$ 当且仅当满足 $sum_r=sum_{l-1}$ 和 $sum_{l-1}\leq sum_{i}(i\in[l,r])$。

显然第一个条件比较好维护，第二个条件是一个类似于范围的东西，所以先处理第二个条件比较好。

那么我们怎么来找出满足这两个条件的序列呢？

我们可以枚举左端点 $l$，然后找 $r$，为什么不用 $r$ 呢？我们发现判断与前缀有关与后缀无关。

第二次转换

在考虑满足第二个条件之前，我们还有一个棘手的问题：

我们还要转换一下，我们发现对于 $l$ 可能有多个 $r$ 是合法的，比如 $\texttt{()()()}$ 这种括号序列。

这是怎么回事呢？我们发现 $l$ 匹配了第一个答案 $r_1$ 之后，后面可能会并列其他的括号序列，只有这种情况，这个原因很简单，不证明。

我们发现对于其他的 $r$，我们完全可以去掉 $[l,r_1]$ 这个部分，由 $r_1+1$ 开始向后匹配，方案数是从 $l$ 匹配的方案减去一（因为你不能向前匹配 $r_1$）。

收到启发我们可以求出 $r_1$ 然后从后向前求出 $f_i=f_{r_1+1}+1$。

第二个条件

好了，接下来考虑满足第二个条件，我们怎么求出限制范围？

我们发现说起来第一个小于本项的好像维护起来没什么头绪，但是我们仔细观察，我们会发现边界是很有特点的！

因为我们的前缀和每次不是加一就是减一，所以第一个小于本项一定为 $sum_{l-1}-1$ 啊！

那边界不就很好求了？我们考虑维护一个我们后面 $fir_x$ 表示 $sum_i=x$ 合法的一个最小的 $i$。

可以倒序去做（这道题很多倒序啊），来维护。

最后就求出了一个边界了，由于这道题字符串不唯一，所以我们要对于 $l$ 取所有字符串中的边界最小值。

第一个条件

第一个条件就很简单了，但是第一条不是一个告诉我们“不可以”的条件，而是让我们“怎么做”的条件，所以和第二个条件的维护略有不同。

我们求出一个最小的 $r$ 使得对于每个字符串 $sum_r=sum_{l-1}$，说白了，我们把所有字符串的前缀和摆成二维表格，我们怎么快速判断两列的信息是否相同？

相信“快速判断”“信息相同”应该可以让你快速想到哈希，我们用哈希来存储一列的信息，然后用第二个条件的方式来做。

由于值域比较大，用 map 维护是一个不错的选择，我们就可以找到第一个和当前列完全相同的一列。

注意我们需要和第二个条件结合，如果我们维护出的 $r_1$ 超越了边界，那么一定是无解的，因为我们这个已经是最小解了，所以我们用各种小手段阻止统计即可。

求出 $r_1$ 之后保存即可，后面倒序统计答案用。

时间复杂度懒得算，大概是 $\mathcal O(nm\log m)$ 的。

代码实现

注意保存 $i$ 对应的 $r_1$ 是代码的 nxt 数组。

#include <bits/stdc++.h>
#define LL long long
using namespace std;
const LL M = 15;
const LL N = 5e4 + 5;
const LL inf=1e9;
const LL mod=1e9+7;
LL n, m, sum[M][N],ans,fir[N*4],lim[N*4],nxt[N*4],hsh[N],f[N];
char s[M][N];
map<LL,LL>ma;
int main() 
{
	scanf("%lld%lld", &n, &m);
	for (int i = 1; i <= n; i++) {
		scanf("%s", s[i] + 1);
		for (int j = 1; j <= m; j++) {
			if (s[i][j] == '(')sum[i][j] = sum[i][j - 1] + 1;
			else sum[i][j] = sum[i][j - 1] - 1;
			hsh[j]=(hsh[j]*13+sum[i][j])%mod;
		}
	}
	memset(lim,127,sizeof(lim));
	for(int i=1;i<=n;i++)
	{
		memset(fir,127,sizeof(fir));
		for(int j=m;j>=1;j--)
		{
			fir[sum[i][j]+N]=j;
			lim[j]=min(lim[j],fir[sum[i][j-1]-1+N]);
		}
	}
	for(int i=m;i>=1;i--)
	{
		nxt[i]=ma[hsh[i-1]];
		ma[hsh[i]]=i;
	}
	for(int i=m;i>=1;i--)
	{
		if(nxt[i]&&nxt[i]<lim[i])
		{
			f[i]=f[nxt[i]+1]+1;
			ans+=f[i];
		}
	}
	printf("%lld",ans);
}