#ICPC01N. 基于值域预处理和矩阵快速幂加速的仙人掌上建模字典树树上dp优化的可持久化珂朵莉树区间操作次数gcd强制在线查询

基于值域预处理和矩阵快速幂加速的仙人掌上建模字典树树上dp优化的可持久化珂朵莉树区间操作次数gcd强制在线查询

题目描述

题面意思和标题一点关系都没有哈。

mqc有一个由来已久的历史遗留问题,是当年邓老师在饭桌上喝高了深入剖析出来的。

题面简单来说就是给定一个由中括号和小括号组成的字符串,求出其中最长的合法子串长度。

()[] 是合法的字符串。

A 是括号匹配的串,则 (A)[A] 是合法的字符串。

AB 都是括号匹配的字符串,则 AB 也是合法的字符串。

(子串是字符串中连续的一段字符)

输入格式

一个字符串 SS

输出格式

一行一个整数,表示最长的合法字符串长度。

([)][()]
4

数据规模与约定

对于 100%100\% 的数据,0S1060 \le |S| \le 10^6