因为只有std，没有自我实现，所以是无码专区
主要是为了训练思维能力
solution才是dls正解，但是因为只有潦草几句，所以大部分会有我自己基于正解上面的算法实现过程，可能选择的算法跟std中dls的实现不太一样。
std可能也会带有博主自己的注释。
problem
给定一个由左右括号构成的字符串 s s s，对于每一个位置 i i i，定义 a n s i : ans_i: ansi: 有多少个子串满足这个子串是一个合法的括号序列，并且 i i i 这个位置在子串中。
合法的括号序列定义：
- 空串合法。
- 如果 S S S 合法，那么 ( S ) (S) (S) 也是合法的。
- 如果 S , T S,T S,T 合法，那么 S T ST ST 也是合法的。
由于答案很大，输出 ∑ i = 1 ∣ S ∣ ( i ⋅ a n s i m o d 1 0 9 + 7 ) sum_{i=1}^{|S|}Big(i·ans_imod{10^9+7}Big) ∑i=1∣S∣(i⋅ansimod109+7)，注意是先取模再相加，相加后并不需要取模。
∣ S ∣ ≤ 1 0 7 , 1 s , 512 M B |S|le 10^7,1s,512MB ∣S∣≤107,1s,512MB。
my idea
套路的，将括号序列转化为 ± 1 ±1 ±1 分数序列，左括号为 + 1 +1 +1，右括号为 − 1 -1 −1。并求前缀和
当一个串为合法括号序列，当且仅当每个位置的前缀和都不小于 0 0 0 ，且最后一个位置的前缀和恰好为 0 0 0。
保证了没有中途右括号个数多于左括号个数，以及最后左右括号个数匹配，显然这是充要条件。
考虑枚举合法括号序列的左端点。
可以肯定的是，被枚举的位置 i i i 本身首先得是个 (。
通过某种手段快速找到 i i i 后面的第一个小于 0 0 0 的前缀和位置 j j j。因为从 j j j 开始后面就一定不合法了。
注意以下的前缀和若无特殊说明，都是指以 i i i 开始的前缀和，所以应该满足 s u m j − s u m i − 1 < 0 sum_j-sum_{i-1}<0 sumj−sumi−1<0。
显然， j j j 位置一定是个 )，且 [ i , j ) [i,j) [i,j) 一定是一个合法括号序列。当然这个性质没有什么用。有用的只是 j j j 的位置。
特殊地，如果一直到最后 ∣ S ∣ |S| ∣S∣ 都没找到，就返回 ∣ S ∣ + 1 |S|+1 ∣S∣+1 即可。
考虑二分，但很容易发现这并不具有连续性，错误。
考虑线段树，相当于在 i i i 时去考虑小于 s u m i − 1 sum_{i-1} sumi−1 的 s u m j sum_j sumj。
具体而言：
从后往前做，到 i i i 时线段树上储存的是 [ i , n ] [i,n] [i,n] 的前缀和（此前缀和是指从 1 1 1 开始的）。
线段树是权值线段树，每个叶子权值储存的是距离 i i i 最近的下标 j j j。
所以查询就是在线段树上 [ 1 , s u m i − 1 ) [1,sum_{i-1}) [1,sumi−1) 区间查询最小的节点权值。
即以权值为线段树上的下标，以下标为线段树上的权值。
维护区间最小值。
修改：每次 i i i 前移 − 1 -1 −1，就把 i i i 的前缀和对应的线段树上叶子节点权值更改为 i i i。
确定了整个大区间，考虑其中的的合法序列，即
s
[
i
,
k
]
,
i
<
k
<
j
s[i,k],i 显然只需要满足
k
k
k 的前缀和为
0
0
0 即可。 现在的问题是怎么迅速找到这些
k
k
k，并快速计算贡献。 先考虑快速计算贡献，显然
[
i
,
k
]
[i,k]
[i,k] 一段合法括号序列会让
i
≤
x
≤
k
ile xle k
i≤x≤k 的
a
n
s
x
ans_x
ansx 都
+
1
+1
+1。 所以这里采取差分手段，对
a
n
s
k
+
1
,
a
n
s
i
−
1
−
1
ans_k+1,ans_{i-1}-1
ansk+1,ansi−1−1，最后的时候来一次后缀和，每个
a
n
s
x
ans_x
ansx 都是正确的了。 最后就只剩下迅速找到这些
k
k
k 的问题了。 一开始就将所有的前缀和
s
u
m
i
sum_i
sumi（这里的前缀和是指以
1
1
1 开始的）桶排序。 即以
s
u
m
i
sum_i
sumi 为桶下标分装所有的前缀和，用 vector 存储，桶内放的是前缀和下标。 然后从前往后考虑左端点
i
i
i，找到
s
u
m
i
sum_i
sumi 的那个桶，以
j
j
j 为分解线二分出最大的小于
j
j
j 的位置
p
p
p，然后桶内前
p
p
p 个的点对应的
a
n
s
ans
ans 都可以差分
+
1
+1
+1。 显然也不能枚举
1
∼
p
1sim p
1∼p 一个一个加，所以在桶里面也进行前缀和差分，在
1
1
1 位置
+
1
+1
+1，在
p
+
1
p+1
p+1 位置
−
1
-1
−1。 每次在二分之前，都得先在
s
u
m
i
sum_i
sumi 的桶内把第一个元素丢出去，在丢之前又得把差分数组及时传递。 所以在
i
i
i 时，所有桶内都只有
i
+
1
∼
∣
S
∣
i+1sim |S|
i+1∼∣S∣ 的前缀和（这里的前缀和是指
1
1
1 开始的），并且桶内的差分是更新过的， 意思就是如果要扔去某个桶的对头
x
x
x（桶内存的是下标），对头下一个是
y
y
y，那么差分数组更新一下
a
n
s
y
+
=
a
n
s
x
ans_y+=ans_x
ansy+=ansx。 因为第二个部分的桶是从前往后做，第一个部分是从后往前做，顺序不同所以要分开做。 桶内前缀差分，差分完后，桶外后缀差分。 时间复杂度：
O
(
n
log
n
)
O(nlog n)
O(nlogn)。 只能通过
70
%
70%
70% 的数据点
∣
S
∣
≤
1
0
6
|S|le 10^6
∣S∣≤106。 solution 凸(艹皿艹 )
O
(
n
log
n
)
O(nlog n)
O(nlogn) 尼玛思维代码量比
O
(
n
)
O(n)
O(n) 还难。 首先处理一下哪些括号是匹配的，用栈来做。 w(X()X(Z()Z)X(Y()Y()Y)X()X)W ，把括号之间的间隔标号，对于一堆匹配的括号，即合法括号序列，要求两端的标号相同。 问题转化为，有若干个标号，要统计位置
i
i
i 两端有多少对标号是相同的。 对于每个匹配括号
(
)
()
()，对于左括号
i
i
i ，记录一个
u
p
i
up_i
upi，
u
p
i
up_i
upi 是最小的能包含这对匹配括号的另一对匹配括号的左括号位置。 即 (..(..)...)，第一个左括号就是
u
p
i
up_i
upi，这期间要保证不存在
u
p
i
<
x
<
i
,
m
a
t
c
h
(
i
)
<
y
<
m
a
t
c
h
(
u
p
i
)
,
x
,
y
up_i 类似前缀和差分，
a
n
s
u
p
i
→
a
n
s
i
ans_{up_i}rightarrow ans_i
ansupi→ansi。 用
a
i
,
b
i
:
a_i,b_i:
ai,bi: 记录左右的连续可完美匹配的括号。 即 (..()..)(..)(..) 第三个左括号和第三个右括号假设是现在
i
i
i 对应的匹配，那么可以选择第一个左括号到第三个右括号，第一个左括号到第四个右括号。 这就用
a
i
∗
b
m
a
t
c
h
(
i
)
a_i*b_{match(i)}
ai∗bmatch(i) 来统计，具体实现可以看 std。 时间复杂度：
O
(
n
)
O(n)
O(n)。 std
第一次见这种处理，是小生孤陋寡闻了Orzqwqqwqdls题解就给个思路，还是得自己仔细想具体代码算法实现。qwq
#include
