UOJ Logo Universal Online Judge

UOJ

#805. 【UR #25】设计草图

附件下载 统计

在跳蚤国,国王梦想着制造出第一辆伏特多轮(Polycycle)。设计这辆汽车需要构建一个稳固的支撑结构,这个结构像由许多括号串连成的复杂模式,以保证汽车的安全性和稳定性。

在这个挑战中,你需要理解何为合法的括号序列

  1. 单一的一对括号 () 表示一个基础的括号序列。
  2. 如果 $A$ 是一个合法的括号序列,则 ($A$) 也是一个合法的括号序列。
  3. 如果 $A,B$ 都是合法的括号序列,则 $AB$ 也是一个合法的括号序列。

现在,你将得到一串由左括号 (、右括号 ) 以及问号 ? 构成的字符串 $S$,代表伏特多轮的支撑结构的图纸设计草图。我们称 $S$ 的一个区间 $[l, r]$ 是有希望合法的,当且仅当存在一种将该区间内的问号替换为左括号或右括号的方式,使得区间内的字符能按顺序组成一个合法的括号序列。

你的任务是求出 $S$ 有多少个区间 $[l, r]$ 是有希望合法的。

输入格式

输入只有一行,包含一个字符串 $S$。

输出格式

输出一行一个整数,表示答案。

样例一

input

(())

output

2

explanation

这组样例合法区间为$[1,4]$和$[2,3]$。

样例二

input

??????????

output

25

explanation

这组样例$[l, r]$ 是有希望合法的当且仅当其为长度为偶数的非空区间

长度为$i$的区间有$n-i+1$个,$n$为字符串$S$长度。故答案为$\sum_{i=1}^{n/2}{n-2i+1}=25$。

样例三

input

(??)??

output

8

explanation

这组样例的有希望合法的区间有$[1,2]$,$[1,4]$,$[1,6]$,$[2,3]$,$[2,5]$,$[3,4]$,$[3,6]$,$[5,6]$,共$8$个区间。

数据范围

对于全部数据:记 $n=|S|$,$1\leq n \leq 10^6$。

子任务编号 $n\leq$ 特殊性质 分值
$1$ $10^6$ $S$ 中只含 ? $5$
$2$ $S$ 中不含 ? $10$
$3$ $20$ $15$
$4$ $5000$ $15$
$5$ $2\times 10^5$ $15$
$6$ $10^6$ $S$ 中不含 ) $20$
$7$ $20$

时间限制:$1\texttt{s}$

空间限制:$512\texttt{MB}$