P3059 [USACO12NOV] Concurrently Balanced Strings G 题解

· · 题解

前言

现在是 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);
}