CF1610G AmShZ Wins a Bet

· · 题解

蓝有一个括号串 S，其中括号串定义为仅由 ( 和 ) 组成的字符串。

现在她进行了任意次如下操作：

  • 将 S 分为三个可以为空的连续子串 A,B,C，接着将 S 变为一个新串 A(B)C（即在 B 前加上左括号，在 B 后加上右括号）。

接着，她给出了经过她任意次操作后的括号串 S，她希望你能还原出原串 S'，使得 S' 的字典序最小。

对于两个字符串 a 和 b，若 a 字典序比 b 小，那么满足如下条件：

  • 令 i 为最小的数使得 a_i\neq b_i，那么 a_i 为左括号。

本题数据满足：1 \leq |S| \leq 3\times10^5。

容易发现只要移除了 S_i,S_j，那么 \forall i<k<j，S_k 都会移除，这是因为如果移除了 (?...)：

因此移除的一定是一些连续的合法的括号序列。

设 to_i 表示 [i,to_i] 这段区间构成合法的括号序列，设 f_i 表示 [i,n] 移除之后字典序最小的串，有

直接 dp 可以做到 O(n^2)。

如果要用数据结构优化，其实是要解决如下问题：

对于一个字符串 S，可持久化地支持：

  • 在某个版本前面添加字符。
  • 比较第 i 个版本和第 j 个版本的字典序大小。（其实就是求 LCP 长度）

暴力上可持久化平衡树可以做到双 log（二分 + 平衡树维护哈希）。

上面的做法大问题是，二分和平衡树的 log 是不能兼容的（因为这时两边结构不同不能平衡树上二分）。有没有什么方法不需要这么 monstrous 的数据结构？

考虑一个更显然的类似问题：

对于序列 S，支持在前面添加数、求区间最小值。

在加入数的过程中动态维护一个 ST 表，加入一个数就 O(\log n) 预处理一下新前缀的 ST 表。

而且这个做法也可以可持久化，把 ST 表建成树上倍增数组类似物。并且，ST 表的结构决定了它可以容下在不同地方开始的二分：将其换为倍增即可。

回到原问题，套用这个做法，倍增维护哈希值即可。

具体地，开两个倍增数组，分别维护 f_i 的第 2^j 位在原串中的位置、f_i 的 [0,2^{j-1}] 的哈希值。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int B=233,mod=998244853;
string s,f[300005];
int st[300005],top,n,to[300005],p[300005][20],hsh[300005][20],pw[300005]={1},S[300005];
int main(){
    cin>>s,n=s.length();
    for(int i=1;i<=n;i++)pw[i]=1ll*pw[i-1]*B%mod;
    for(int i=0;i<n;i++){
        if(s[i]=='(')st[++top]=i;
        else {
            if(top)to[st[top]]=i+1,top--;
        }
    }
    p[n][0]=S[n]=n;
    for(int i=n-1;i>=0;i--){
        p[i][0]=S[i+1],hsh[i][0]=s[i],S[i]=i;
        for(int j=1;j<=18;j++){
            p[i][j]=p[p[i][j-1]][j-1];
            hsh[i][j]=(hsh[i][j-1]+1ll*hsh[p[i][j-1]][j-1]*pw[(1<<j-1)])%mod;
        }
        if(to[i]){
            int x=i,y=S[to[i]];
            for(int j=18;j>=0;j--){
                if(hsh[x][j]==hsh[y][j]){
                    x=p[x][j],y=p[y][j];
                }
            }
            if(y==n||(s[x]>s[y]))S[i]=S[to[i]];
        }
    }
    int x=S[0];
    while(x<n)cout<<s[x],x=p[x][0]; 
}