因为这篇题解原文是用 Markdown 写成，在 我的博客 上面可能会有更好的阅读体验

考虑一个合法的括号序列长什么样子：(...) ，即由外面的括号和里面的部分组成，有用的信息来自于内部，于是我们关注内部可以由什么组成：

根据定义，一个合法的括号序列，内部可以是：S、AA、ASA、A、AS、SA，其中，AA 和 ASA 比较特殊，因为它们本身就是一个 A，信息被包含在 A 中。于是得到一个公式：

$$A_{i, j} = A_{i + 1, j - 1} + S_{i + 1, j - 1} + AS_{i + 1, j - 1} + SA_{i + 1, j - 1} \notag$$

接下来，我们考虑这些部分的信息如何维护：

1. 对于 A：我们若将这个递推公式深究到底，会得到什么？什么情况下就递归不下去了？也许最后的 A 是一个 ()，这当然合法，并且这个信息无法从别处递推来，于是，对于这个，我们在遇到的时候需要统计一下。或者，(S) 也是一个合法的括号序列，再往下深究，就是一个 S ，就是说，如果 (S) 放到上面的公式中，最后会得到一个 S 的值，显然这个值得是 $1$
2. 对于 S：经过上面的讨论，$\forall i, j \in \mathbb{N^+}, S_{i, j} = 1$ 而这个等式成立的前提是 $i, j$ 中间的部分完全由 '*' 组成

对于 AS，SA，ASA，AA 这些由 A 和 S 这两个比较基本的部分组成的部分，我们用乘法原理，可以求出它们的值。即：

$$AS_{i, j} = \sum_{i \le k \le j}A_{i, k} \times S_{k + 1, j} \notag \\ SA_{i, j} = \sum_{i \le k \le j}S_{i, k} \times A_{k + 1, j} \notag \\ ASA_{i, j} = \sum_{i \le k \le j}A_{i, k} \times SA_{k + 1, j} \notag \\ AA_{i, j} = \sum_{i \le k \le j}A_{i, k} \times A_{k + 1, j} \notag \\$$

需要注意的是，如果我们将 AA 和 ASA 的信息累加到 A 中，会导致原来的信息被覆盖掉，导致出错，所以在程序实现中我们需要用一个数组来备份合并操作之前的信息。

$ \begin{aligned}ans &= \frac{\binom{num_l}{2} + \binom{num_{l + 1}}{2} + \dots + \binom{num_r}{2}}{\binom{r - l + 1}{2}} \\ &= \frac{num_l(num_l - 1) + num_{l + 1}(num_{l + 1} - 1) + \dots + num_r(num_r - 1)}{(r - l + 1)(r - l)} \\ &= \frac{(num_l^2 + num_{l + 1}^2 + \dots + num_r^2) - (num_l + num_{l + 1} + \dots + num_r)}{(r - l + 1)(r - l)} \\ &= \frac{(num_l^2 + num_{l + 1}^2 + \dots + num_r^2) - (r - l + 1)}{(r - l + 1)(r - l)} \end{aligned} $

而

$ (n + 1)^2 = n^2 + 1 + 2n \\ (n - 1)^2 = n^2 + 1 - 2n $

所以对于每一个询问 $[l, r]$，我们只需要将当前询问的分子加上 $2n + 1$ 即可 $O(1)$ 地将答案扩展至 $[l, r + 1]$ 或 $[l - 1, r]$，而对于缩小区间的操作，同理。

于是，我们可以用 $\mid l' - l \mid + \mid r' - r \mid$ 次操作转移至下一询问区间。

而利用分块，将所处分块作为第一关键字，将右区间作为第二关键字，可以实现 $O(n \sqrt n)$ 的时间复杂度。

前置知识

$Lucas$ 定理，中国剩余定理（$CRT$），费马-欧拉定理。

费马-欧拉定理

设 $a,m$ ∈ $N^+$，且 $gcd$（$a,m$）= $1$，则我们有： $a^φ$≡$1$($/mod m$)。

其中，φ($m$) 称为对模 $m$ 缩系的元素个数。

此外，$a$ 对模 $m$ 的阶必整除 $φ$($m$)。

证明如下：（自己度娘）

https://baike.baidu.com/item/%E6%AC%A7%E6%8B%89%E5%AE%9A%E7%90%86/891345

Lucas定理

中国剩余定理（CRT）

题面概述

存在一个整数 $N$，对于约数$d$（$d|N$），求 $C_d^n$ 对 $999911659$ 取模的值

思路

$O(N)$预处理，$O(1)$查询：

先求出模 $p$ 意义下的阶乘，逆元以及逆元阶乘（因为求逆元满足积性函数）。

对于任意一个小于p的组合数 $C_m^n$，可以直接用 $jc[m] /times invjc[n] /times invjv[m-n]求出，其中 $jc[i]$ 指到 $i$ 的阶乘, $invjc[i]$ 指到 $i$ 的阶乘逆元

代码就不贴了……

0ms，0Mid

斜率优化$DP$ + 二分查找  时间复杂度：$O(N*logN)$  

与 $任务安排2(cogs 1162)$ 一题不同的是，$T$ 可能是负数，意味着 $sumT$ 不再具有单调性，从而需要最小化截距的直线斜率 $S+sumT[i]$ 不具有单调性。故，不能在单调队列中只保留凸壳上“$ 连接相邻两点的线段斜率 $”大于 $S+sumT[i]$ 的部分，而是必须维护整个凸壳。

这样一来，就不需要在队头把斜率与 $S+sumT[i]$ 比较。

队头也不一定是最优决策，我们可以在单调队列中二分查找，求一个位置 $p$，$p$ 左侧线段斜率比 $S+sumT[i]$

小，右侧斜率比 $S+sumT[i]$ 大，$p$ 就是最优决策。

队尾维护斜率单调性的方法与 $任务安排2$ 一题相同。

解法一  时间复杂度$O(N^3)$  期望得分：$60$

1、求出 $T,C$ 的前缀和$sumT[i]$和$sumC[i]$;

2、设$f(i,j)$表示：把前 $i$ 个任务分成 $j$ 批执行的最小费用;

3、以第 $j-1$ 批和第 $j$ 批任务的分界点为$DP$的“$决策$”，状态转移方程为：

$f(i,j) = min\{ f(k,j-1) + (S*j + sumT[i]) * (sumC[i]-sumC[k]) \} (0<=k<j)$

其中，$(S*j + sumT[i])$为第 $j$ 批任务完成的时间，$(sumC[i]-sumC[k])$为第 $j$ 批（$[k+1,i]$）任务的费用系数之和。

解法二  时间复杂度:$O(N^2)$  期望得分：$100$

本题并没有规定把任务分成多少批，解法$1$之所以需要批次 $j$ ,是因为需要知道机器启动了多少次(每次需要启动时间$S$),从而计算出任务 $i$ 所在批次的完成时刻。

事实上，执行一批任务时，不容易直接得知此前机器启动了几次。但我们知道，机器因执行该批次而花费的时间 $S$，会累加到之后所有任务的完成时刻上。

设：$f(i)$ 表示把前 $i$ 个任务分成若干批执行的最小费用，状态转移方程为：

$f(i) = min\{ f(j) + sumT[i] * (sumC[i]-sumC[j]) + S*(sumC[N]-sumC[j]) \} (0<=j<j)$

在上式中，$[j+1,i]$范围内的任务在同一批完成，$sumT[i]$是忽略机器启动时间时，该批任务的完成时刻。

因为该批任务的执行，机器的启动时间 $S$ 会对第 $j+1$ 个之后的所有任务产生影响，故我们需要把这部分补充到费用中。

也就是说，我们没有直接求出每批任务的完成时刻，而是在一批任务“开始”对后续任务产生影响时，就先把费用累加到答案中。这是一种名为“费用提前计算”的经典思想。

题解来自《算法竞赛进阶指南》$P322$

$f(i,j)$: 安排前 $i$ 个工匠粉刷前 $j$ 块木板(可以有空着不刷的),工匠们能获得的最大报酬;

(1)第 $i$ 个工匠可以什么也不刷,此时：$f(i,j) = f(i-1,j)$;

(2)第 $j$ 块木板可以 空着 不刷,此时：$f(i,j) = f(i,j-1)$;

(3)第 $i$ 个工匠粉刷 $[k+1,j]$ 的木板，总数不超过$L_i$且必须包含$S_i$，

故：$k+1<=S_i<=j  即  k<=S_i-1;  j-k<=L_i  即  k>=j-L_i$

$f(i,j)=max\{ f(i-1,k) + P_i*(j-k) \}  (j-L_i<=k<=S_i-1, j>=S_i)$

优化：（细节请参考《算法竞赛进阶指南》 P315）

考虑内层循环$j$以及决策$k$时,可以把外层$i$看作定值,状态转移方程可改为：

$f(i,j)=P_i*j + max\{ f(i-1,k)-P_i*k \} (j-L_i<=k<=S_i-1, j>=S_i)$

当$j$增大时,决策 $k$ 的取值范围上界$S_i-1$不变，下界$j-L_i$变大，按与“最大子序列和”一题类似的想法，我们比较任意$2$个决策$k_1$和$k_2$，不妨假设$k_1<k_2<=S_i-1$：

因为$k_2>k_1$，随着j增大，$k_1$会比$k_2$更早从范围$[j-L_i,S_i-1]$中被排除，如果还满足:

$f(i-1,k_1)-P_i*k_1<=f(i-1,k_2)-P_i*k_2$,那么就意味着$k_2$比$k_1$更优且存活期更长。

这种情况下,$k_1$就是无用决策，从候选集排除即可。

综上所述，可以维护一个决策点$k$单调递增，数值$f(i-1,k)-P_i*k$单调递减的队列。

只有队列中的决策才有可能在某一时刻成为最优决策。

该单调队列支持如下操作：

1、$j$变大时，检查队头，把小于$j-L_i$的决策出队；

2、需要查询最优决策时，队头即所求；

3、新决策需要加入候选集时，在队尾检查$f(i-1,k)-P_i*k$的单调性，把无用决策出队，最后新决策入队。

具体操作：

内循环开始时($j=S_i$)，建立空队列，把$[max(S_i-L_i,0) , S_i-1]$中的决策加入候选集(操作$3$).对于每个$j=S_i$~$N$,

检查决策合法性(操作$1$),然后取队头为最优决策(操作$2$)进行状态转移。

每个决策最多入队、出队$1$次，故转移时间复杂度均摊$O(1)$,整体时间复杂度$O(NM)$