CSP2024 前做题情况 1
fzitb7912
·
·
个人记录
10.12 开始写，每天做的题都在这里了。
AT_arc058_b
考虑组合数。
对于从 (1,1) 走到 (n,m) 的方案数，显然是 C_{(n-1+1)+(m-1+1)-2}^{(n-1+1)-1/(m-1+1)-1}。那么考虑枚举一个行 i(1\le i \le n-a)，我们需要从 (1,1) 走到 (i,b)。这样能够使得我们的每一步都没有走到不可走的区域，然后从 (i,b) 走到 (n,m)。时间复杂度是 O(n\log n) 的。
AT_arc059_b
考虑答案上下界。
答案下界显然是 2，因为要求 l <r。对于一个满足条件的子串 t，令其众数为 x。有 2 种情况：
-
存在连续的 i,i+1，使得 t_i=t_{i+1}=x。此时直接构造 t'=t_it_{i+1} 是对的。
-
不存在连续的 i,i+1，使得 t_i=t_{i+1}=x。那么一定存在 t_{i}=t_{i+2}=x，否则众数不为 x。证明简单。此时构造 t'=t_it_{i+1}t_{i+2} 是对的。
所以答案上界为 3。然后暴力枚举 i 即可。时间复杂度是 O(|s|) 的。
AT_arc061_b
考虑暴力枚举。
发现 n,m 很大，但是对于一个黑点 (i,j) 能够贡献到的 3 \times 3 的网格数量很少。所以对于每一个黑点 (i,j)，我们去枚举它能贡献的所有 3 \times 3 的网格的中点 (x,y)。改变一下它的黑点数量，随便维护一下即可。对于一个 n \times m 的网格，它里面 3 \times 3 的网格数量为 n \times m -2 \times (n+m) +4。时间复杂度 O(k\log V)。
AT_arc064_b
很难啊。
题目翻译没有说不能选两端的字符，但是就是不能选。
如果没有不能选两端的限制，考虑怎么做。对于当前字符串状态 s，若存在一个 i，使得 s_{i-1} \ne s_{i+1}。直接删掉。否则字符串 s 一定是 2 种字符交错排列的，删掉头即可。那么，对于没有限制的情况，当 |s| 是奇数时，先手必胜；反之同理。
现在考虑不能选两端的情况。那就相当于删掉了字符串的头和尾，然后没有限制地删。如果删头的时候出现了两个字符相同的情况且删尾也有同样的情况。那么此时字符串长度为奇数，且原字符串的头和尾均相同。先手必败。反之同理。
AT_arc066_b
好难啊。真的只有蓝嘛。
考虑 DP。定义状态函数 f_{i,j} 表示从高往低第 i 为，a+b=j 时不同的 a~ xor~ b 的值。然后考虑第 i 位放什么：
-
-
-
然后就没有了，观察到有用的状态数不多，直接暴力即可。这题记忆化搜索就行了，纯暴力是 TLE 的。
AT_abc051_d
### AT_abc054_d
直接暴力地 DP 即可。没什么好说的。
### CF833B
考虑 DP。
定义状态函数 $f_{i,j}$ 表示前 $i$ 个数，分成 $j$ 段的最大价值。有：$f_{i,j}=\max(\{f_{k,j-1}+val(k+1,i)|0 \le k <i \})$。难点在于求 $val(i,j)$。发现这玩意满足四边形不等式，但是直接记录 $pre_i$ 表示颜色 $c_i$ 在上一次的出现位置，那么在区间 $[pre_i+1,i]$ 的 $val(x,y)$ 都会增加 $1$ 的贡献。直接放线段树上维护，优化 DP 即可。复杂度 $O(nk\log n)$。
### AT_arc108_e
考虑区间 DP。
定义状态函数 $f_{l,r}$ 表示钦定选择了 $a_l,a_r(a_l<a_r)$ 时，区间 $(l,r)$ 还能选择的期望数量。则有：$f_{l,r}=1+\frac{1}{k}\times \sum\limits_{l < p < r\land a_l < a_p < a_r}^{}f_{l,p}+f_{p,r}$。其中 $k$ 表示 $p$ 的数量。不难发现，$\sum$ 中的二者独立。所以当我们枚举 $l$ 后枚举 $r$ 时，我们可以通过任意方式快速得到 $k$，$\sum\limits_{l < p < r\land a_l < a_p <a_r}^{}f_{l,p}$ 和 $\sum\limits_{l < p < r\land a_l < a_p <a_r}^{}f_{p,r}$。然后加起来就行了。使用树状数组的时间复杂度是 $O(n^2\log n)$ 的。
### CF321E
考虑 DP。
定义状态函数 $f_{i,j}$ 表示前 $i$ 只狐狸分成 $j$ 组的最小代价。那么有转移方程：$f_{i,j}=\min(\{f_{k-1,j-1}+w(k,i)|0 < k\le i\})$。发现 $w(i,j)$ 满足四边形不等式，证明：
>
>定义 $sum(i,j)=\sum\limits_{x=i}^{j}\sum\limits_{y=i}^{j}a_{x,y}$。那么有：$w(a,c)+w(b,d)=\frac{sum(a,c)+sum(b,d)}{2},w(a,d)+w(b,c)=\frac{sum(a,d)+sum(b,c)}{2}$。其中有：$sum(a,d)=sum(a,c)+sum(a,b)+sum(c,d)+sum(b,d)-sum(b,c)$。所以 $w(a,d)+w(b,c)=\frac{sum(a,c)+sum(a,b)+sum(c,d)+sum(b,d)}{2}\ge w(a,c)+w(b,d)$。
然后对于每一组分治即可。具体地，对于当前区间 $[l,r]$ 我们能够得到决策区间 $[pl,pr]$，使得任意一个 $l \le i \le r$，都有 $pl \le p_i \le p_r$。能够先算出来 $p_{mid}$ 的值，那么根据决策单调性就有 $mid$ 左边的所有点的决策区间变成 $[pl,p_{mid}]$，右侧同理。所以时间复杂度是 $O(nk\log n)$ 的。
### P9338
这题怎么这么难。
考虑 DP。
首先发现将 $S$ 分成 $<k$ 个子序列与分成 $=k$ 个子序列是等价的。所以只需要求最少的子序列数量，使得它 $\le k$。将 $S$ 看成 $n \times n$ 的网格中的一条路径，将 $A$ 看成向上走，$B$ 看成像右走。那么一次交换 $BA$ 的操作就会使右上变成上右。一条路径有解首先需要使得这条路径始终在对角线的上方。
根据贪心，分成的区间数量至少是这条路径的拐点数量。每次往右拐相当于一个区间。继续观察可以发现，一个区间的代价为这个拐点到原区间的拐点中间的面积数量。
然后就能 DP 了。令 $s_i$ 为第 $i$ 个 $B$ 之前 $A$ 的数量，$S_i=\sum\limits_{j=1}^{i} s_i$，$cnt_i$ 为 $s_j \le i$ 的 $i$ 的数量，$sum_i$ 为 $s_j \le i$ 的 $s_i$ 的和。 那么就有：$w(l,r)=(cnt_{r-1}-(l-1))\times (r-1) -(sum_{r-1}-S_{l-1})$。
把式子拆开：
$$
w(l,r)=(cnt_{r-1}-(l-1))\times (r-1) -(sum_{r-1}-S_{l-1})\\
w(l,r)=cnt_{r-1}\times (r-1)-(l-1)\times (r-1)-sum_{r-1}+S_{l-1}
$$
定义状态函数 $f_{i,j}$ 表示前 $i$ 个数分成 $j$ 段的最小代价，有：$f_{i,j}=\min(\{f_{k-1,j-1}+w(k,i)|1 \le k \le i\})$。然后就能够斜率优化。又因为 $w(l,r)$ 满足四边形不等式，所以套用 wqs 二分可以做到 $O(n\log n)$。
### CF1637G
/bx 多头老师
不容易观察到最终的数是 $2^k$。只要我们能够构造出来一个 $0$，那么就可以通过倍增的方式将所有数变成 $2^k$ 了。那么对于每次操作，我们需要找到一组 $(x,y)$，使得 $x+y=2^w(w \le k)$。
考虑如何实现。首先可以找到当前最大的一个数，然后枚举 $k$，使得存在一个 $y=2^k-x$。能够证明该做法一定是正确的。因为如果连最大的数都不行，那么小的数可能不行了。如果大的不行，那么考虑在之后将它操作，也就是继续选择次大的数，并将这个数暂存一下。最后剩余一个数时就是答案了。时间复杂度是 $O(n\log n)$ 的。
### P11184
考虑一个余数 $r$ 满足条件的限制。因为 $p=\frac{n-r}{q}$，且 $ 0 \le r <p$。所以直接求解就行了。
### P11185
按照三种情况分别排序。那么一个同学的最终排名就是这三种情况排名最靠前的一个。
### P11186
考虑对这个表达式建树。对于点 $x$，我们记录它的值 $val$ 与判断符 $c$。分情况讨论：
1. $c$ 是小于号，则一个查询数字 $k$ **小于** $val$ 时答案一定存在于 $x$ 的左子树，反之同理。
2. $c$ 是大于号，则一个查询数字 $k$ **小于等于** $val$ 时答案一定存在于 $x$ 的左子树，反之同理。
如果对于每个询问的 $k$ 都去搜索一遍的话，时间复杂度将会达到 $O(nq)$。考虑优化。
既然在线比较困难，那就离线看看。对于当前节点 $x$，我们能够得到一个询问区间 $[l,r]$，使得这个区间中任意一个 $k_i$ 对应的答案都存在于 $x$ 的子树中。那么，依旧分情况讨论：
1. $c$ 是小于号，则查询区间中数字 $k_i$ **小于** $val$ 时答案一定存在于 $x$ 的左子树，反之同理。
2. $c$ 是大于号，则查询区间中数字 $k_i$ **小于等于** $val$ 时答案一定存在于 $x$ 的左子树，反之同理。
记最后一个答案在 $x$ 的左子树中的询问下标为 $w$，则 $[l,w]$ 的答案一定在 $x$ 的左子树中，$(w,r]$ 的答案一定在 $x$ 的右子树中。分治下去即可。这样的话时间复杂度是 $O(q+n\log n)$ 的。
注意特判 $n=0$ 的情况。
### P11187
考虑 DP。
定义状态函数 $f_{i,0/1}$ 表示子序列的最后一位的值为 $i$，且已经/没有连续两个 $i$ 时的最大子序列长度。那么我们枚举 $x$，有：$f_{a_x,0}=f_{a_x,1}+1,f_{a_x,1}=\max(\{f_{i,0}|i \ne a_x\})+1$。前者直接转移，后者拿一个线段树随便优化就行了。这样的时间复杂度是 $O(n\log n)$ 的，但是存在线性做法。
### P11188
考虑 DP。
首先发现性质：当一个数的位数 $>10$ 时，进行操作一一定优于操作二。因为数据范围有：$1 \le v_i \le 10^5$。
那么操作二时数的长度就不会超过 $10$ 了。定义状态函数 $f_{i,j}$ 表示从后往前第 $i$ 位，保留了 $j$ 位时删完的最小代价。那么有：$f_{i,j}=\min(f_{i,j},f_{i+1,j}+v_{s_i}),f_{i,j+1}=\min(f_{i,j+1},f_{i+1,j}+s_i\times 10^j)$。时间复杂度 $O(10 \times n)$。
### P11190
考虑答案长什么样子。
对于不相同的一组 $s_i,s_j$，我们可以将它们拼起来。那么就会得到若干个二元组，然后剩下一些相同的 $s_i,s_j$。此时我们只需要考虑如何将剩下的字符放进这些二元组内，如果可行则答案一定是二元组数量。
令剩下的字符为 $x$，如果有一组 $(s_i,s_j)$，使得 $s_i \ne x $ 且 $x$ 中有些的下标大于 $j$，那么可以将它们全部拼到这个二元组后面。另一种情况同理。
如果还剩有字符，考虑替换两个二元组 $(s_{x1},s_{y1})$ 和 $(s_{x2},s_{y2})$。使得其能够容下更多的字符。
如果还有，那么无解。可以证明，无解的情况只有形如：$aaa\dots aaa$ 和 $aaa \dots b \dots aaa$。也就是无法分解的回文串。
之后就只剩下模拟了。注意，拼二元组的时候需要优先将当前的众数与其它的字符进行拼接，以保证能够容下更多的字符。实现难度不大，细节较多。时间复杂度 $O(n\log n)$。
### CF2025A
如果操作 $1$，最优方案显然是先弄个最长公共前缀然后自己弄自己的。那么把最长公共前缀求出来就行了。时间复杂度 $O(n)$。
### CF2025B
数感好的秒出答案。数感不好的果断打表观察规律。发现对于 $C_{i,j}$，若 $j=0\lor i$，则其值为 $1$，否则为 $2^j$。时间复杂度 $O(n\log n)$。
### CF2025C
注意读题。发现题目中有这么一句话：Monocarp 可以取任何一张符合条件的牌，不管它在牌组中的位置如何。
那么这题就好做了。不考虑顺序，直接将 $A$ 序列排序。然后使用双指针即可。时间复杂度 $O(n\log n)$。
### CF2025D
注意到除了能增加智力或力量的那 $m$ 个点外，其它的点貌似没什么用。令 $p_i$ 表示第 $i$ 个能获取属性点的下标。定义状态函数 $f_{i,j}$ 表示前 $i$ 个点中，智力为 $j$ 时能够通过的最多的检查点数量。
那么有转移方程：$f_{i,j}=\max(f_{i-1,j}+w1(p_i,p_{i+1},j)+w2(p_i,p_{i+1},i-j),f_{i-1,j-1}+w1(p_i,p_{i+1},j)+w2(p_i,p_{i+1},i-j))$。其中 $w1(l,r,k)$ 为区间 $[l,r]$ 中检查点所需的智力不超过 $k$ 的数量，$w2(l,r,k)$ 同理。时间复杂度 $O(m^2)$。
### CF2025E
考虑 DP。
注意到对于一种花色 $x(x\ge 2)$，第一个人得到的一定不多于第二个人得到的。因为一旦比第二个人多，那么他一定会剩下一些这种花色的牌，并且用不出去。那么对于第二个人比第一个人得到的该花色的牌多的情况，此时只能由第一个人得到的多的花色为 $1$ 的牌抵消掉。
那么思路就有了。我们只需要求出一个 $g_i$，表示 $2\sim n$ 这些花色中，第二个人比第一个人多 $i$ 张牌的方案数（其它的牌都两两抵消掉了）。然后再求一个 $f_{i}$，表示第一个人比第二个人多 $i$ 张花色 $1$ 的牌的方案数。那么答案就是 $\sum\limits_{i=0}^{m} f_i \times g_i$。
对于 $g_i$，不难发现是由 $f'$ 经过 $n-1$ 次背包转移得到的。因为每种花色对应的方案数相同。这里的 $f'_i$ 和 $f_i$ 的区别仅在于是第二个人比第一个人多 $i$ 张牌。那么只要求出 $f_i$，就能得到 $f'_i$，从而得到 $g_i$ 了。
定义状态函数 $dp_{i,j,k}$ 表示前 $i$ 张牌，发给第一个人 $j$ 张，第一个人比第二个多 $k$ 张的方案数。那么分类讨论：
1. 第 $i$ 张牌给第一个人，有：$dp_{i,j,k}\to dp_{i,j,k}+dp_{i-1,j-1,k-1}$。
2. 第 $i$ 张牌给第二个人，有：$dp_{i,j,k}\to dp_{i,j,k}+dp_{i-1,j,k+1}$。
那么有：$f_i=\sum\limits_{j=0}^{m} dp_{m,j,i}$。
然后 $f'_i$ 和 $g_i$ 就能相继求出来了。时间复杂度 $O(m^3+m^2n)$。
### AT_jag2018summer_day2_i
很显然，有还原的题基本不能用势能分析做。
考虑线段树。
考虑换个方式维护。因为这题目有区间加法和区间除法。我们记录下来每次除法之后，得到的商、余数和除数。即：$c\times b+a=c'$。其中 $c$ 是商，也就是当前的值，$b$ 是除数，$a$ 是余数，$c'$ 是除法前的数也就是被除数。
那么，考虑一种映射：$f(x)=\lfloor\frac{a+x}{b}\rfloor+c$。对于每个数，我们都记录下来最近一次除法或加法后得到的商、余数和除数。那我们就可以快速得到当前这个数实际上的值了。及其分别为 $c,a,b$。
加法操作。直接就是在 $c$ 上面进行加法操作。
除法操作。假设该操作为区间除以 $w$。这里的 $x$ 并未改变，我们需要调整的只有该映射中的 $a,b,c$。所以有：$a'=(a+bc)\bmod bw,b'=bw,c'=\lfloor\frac{a+bc}{bw}\rfloor$。在这里，我们将 $\frac{a}{b}+c$ 写成了 $\frac{a+bc}{b}$，方便计算。然后除法操作就可以直接维护了。
还原操作。我们再维护一个 $rmax$，表示当前节点在最开始的区间 $max$ 值。那么一个还原操作就相当于将当前的 $max$ 值变成 $rmax$，并且清空其映射的参数。记录一个懒标记表示该节点的子树是否需要全部还原即可。
询问操作。直接就是正常的区间询问最大值，不再赘述。
该算法的时间复杂度为 $O(n\log n)$。有一个小细节，就是在我们维护的 $b$ 这个参数比 $3\times 10^8$ 大时，能够证明 $b$ 的增加是无效的。所以可以直接让 $b$ 成为其中一个能够被接受的值。不然可能会 RE 或者 WA。
### P8600
好像是我今年在中山集训的某场模拟赛 T4。当时太菜了，只因没做过套路题。
首先这道题可以转化成求有多少个区间 $[l,r]$，使得 $r-l=\max(a_l,a_{l+1},\dots,a_r)-\min(a_l,a_{l+1},\dots,a_r)$。然后这种问区间数量，且存在区间最大、最小值的题。有一种套路，详见 [AT_abc248_h](https://www.luogu.com.cn/article/mrksztx2) 的题解。第一次遇到这种套路是在做 Norma 的时候。感觉很强啊。
考虑分治。我们枚举左端点 $l$，那么现在已知 $\max(a_l,a_{l+1},\dots,a_{mid})=mx,\min(a_l,a_{l+1},\dots,a_{mid})=mi$。令 $Max_i=\max\limits_{j=mid+1}^{i}a_j,Min_i=\min\limits_{j=mid+1}^{i} a_j$。我们能够通过指针找到最远的一个 $j$，使得 $Max_j \le mx$。也能找到一个最远的 $k$，使得 $Min_k \ge mi$。现在进行分类讨论：
1. $r \le \min(j,k)$。此时区间最小、最大值固定。那么有：$r=mx-mi+l \land mid+1 \le r \le \min(j,k)$。
2. $\min(j,k) < r \le \max(j,k)$。这时有两种情况，以 $j <k$ 为例。此时区间最小值固定，区间最大值与 $Max_r$ 相等。那么有：$l-mi=r-Max_r\land \min(j,k) < r \le \max(j,k)$。
3. $\max(j,k)<r \le R$。此时区间最小值与 $Min_r$ 相等，区间最大值与 $Max_r$ 相等。那么有：$l=r+Min_r-Max_r \land \max(j,k) < r \le R$。
上面的所有满足条件的 $r$ 都可以分别用桶存起来，所以访问是能够做到 $O(1)$ 的。故时间复杂度为 $O(n\log n)$。
### CF526F
将二维问题转化成一维的问题。让 $a_i=j$，那么问题就变成 $P8600$ 了。这能 *3000？？？时间复杂度 $O(n\log n)$。
### P10587
考虑势能线段树。
不难发现，当 $V=5\times 10^5$ 时，小Y 喜欢的数只有 $5$ 个。这里使用两种势能，第一种表示 $x$ 这个数可能成为小Y 喜欢的数的势能，第二种表示 $x$ 这个数达到 $V$ 的势能。
对于区间加法操作。我们令 $nxt_i$ 表示 $i$ 与第一个比 $i$ 大且是小Y 喜欢的数的差。对于每个节点，维护 $mit$ 表示该节点维护的区间中 $nxt_x$ 最小的值。进行分类讨论：
1. $mit > x$。此时势能无影响，且对答案无影响。直接做区间加法即可。
2. $mit \le x$。此时区间总势能至少减 $len$。下传继续维护区间加法。
对于区间乘法操作。每个数的初始势能不大于 $\log V$，一个区间的总势能至少减 $len$。下传继续维护区间乘法。
对于区间覆盖操作。该操作将会使一个区间的两种势能统一，且恢复原来的势能需要 $O(n)$ 的代价。直接进行区间覆盖即可。在这里，对于一个区间所有数都相同的时候，加法操作和乘法操作均能够将该区间视做单点，所以无需下传维护。
对于区间询问。我们因为 $mit \ge 0$，我们记录每个点维护的区间中 $nxt_x=mit$ 的数量，记为 $cnt$。当该点的 $mit=0$ 时，答案即为 $cnt$。否则为 $0$。
根据势能分析，该算法的时间复杂度为 $O(n\log V)$。
### AT_arc059_c
考虑 DP。
发现数据范围不大，定义状态函数 $f_{i,j}$ 表示前 $i$ 个小朋友，一共得到 $j$ 颗糖的愉悦度。那么有：$f_{i,j}=\sum\limits_{k=0}^{j}(f_{i-1,j-k}\times \sum\limits_{w=a_i}^{b_i}w^k)$。
观察式子，发现 $\sum\limits_{w=a_i}^{b_i}w^k$ 可以通过前缀和预处理出来。令 $s_{i,j}=\sum\limits_{k=0}^{i}k^j$。那么转移方程可以写成：$f_{i,j}=\sum\limits_{k=0}^{j}(f_{i-1,j-k}\times (s_{b_i,k}-s_{a_i-1,k}))$。时间复杂度 $O(n^3)$。
### P3605
考虑将树转化成 DFS 序。那么就是查询区间 $[dfn_x,dfn_x+siz_x-1]$ 中比 $p_x$ 大的数的数量了。拿一个主席树，维护的值域线段树。然后直接查询就行了。时间复杂度是 $O(n \log n)$ 的。
### AT_arc060_c
考虑倍增。定义 $f_{i,j}$ 表示从 $i$ 开始尽量往右走，走 $2^j$ 天后能够到达的最远的点。那么对于询问 $a,b$，就是求一个最小的 $x$，使得 $a$ 往右走 $x$ 天后离 $b$ 最近。这个倍增跳的时间复杂度是 $O(n\log n)$ 的。
### AT_arc067_c
考虑 DP。
根据题意就能直接定义状态函数并且正确的一题。定义状态函数 $f_{i,j}$ 表示到 $i$ 个人一组的组，一共分了 $j$ 个人的方案数。那么能够得到转移方程：$f_{i,j}=f_{i-1,j}+\sum\limits_{k=c}^{d}f_{i-1,j-k\times i}\times C_{n-j+k\times i}^{k\times i}\times \frac{\prod\limits_{w=1}^{k}C_{k\times i- (w-1)\times i}^{i}}{k!}$。其中 $f_{i-1,j}$ 表示 $F_i=0$ 的情况。$C_{n-j+k\times i}^{k\times i}$ 表示选出 $k\times i$ 个人的方案数。而 $\frac{\prod\limits_{w=1}^{k}C_{k\times i- (w-1)\times i}^{i}}{k!}$ 表示将这些人分成 $k$ 组的方案数，这里可以简化成 $\frac{\prod\limits_{w=1}^{k}C_{w\times i}^{i}}{k!}$。
考虑快速计算 $\prod\limits_{w=1}^{k}C_{w\times i}^{i}$。发现这是一个前缀积的形式，令 $s_{i,j}=\prod\limits_{k=1}^{i}C_{k\times j}^{j}$，则有：$s_{i,j}=s_{i-1,j}\times C_{i\times j}^{j}$。那么转移方程就可以写成：$f_{i,j}=f_{i-1,j}+\sum\limits_{k=c}^{d}f_{i-1,j-k\times i}\times C_{k\times i}^{n-j+k\times i}\times \frac{s_{k,i}}{k!}$。
因为 $\sum\limits_{k=c}^{d}f_{i-1,j-k\times i}\times V$ 是一个调和级数的形式，所以该算法的时间复杂度为 $O(n^2\log n)$。预处理 $C_{i,j}$ 即可。
### P4269
DP 的转移不难，难点在于去重。令上一次 $a_i$ 出现的位置为 $j$。我们能够得到 $1\sim i-1$ 与 $i$ 形成的上升子序列的数量。而这里面恰好完全包含了 $1\sim j-1$ 与 $j$ 形成上升子序列的数量。而 $a_j=a_i$。所以只有 $j+1 \sim i-1$ 与 $i$ 形成的上升子序列是新增的。所以记录一下上一次 $a_i$ 对应的数量即可。时间复杂度 $O(n\log V)$。
### P6477
对于一个 $r$，我们有 $g_r=\sum\limits_{l=1}^{r}(f_{l,r})^2$。令 $lst_x$ 表示上一次 $x$ 出现的位置。那么 $lst_{a_r}+1\sim r$ 这段区间所有位置的 $f_{l,r}$ 都会增加 $1$，其余位置不变。所以 $g_r$ 比 $g_{r-1}$ 多 $r-lst_{a_r}+2\times \sum\limits_{l=lst_{a_r}+1}^{r}f_{l,r}$。直接维护即可。时间复杂度 $O(n\log n)$。
### P6569
矩阵快速幂。构造 $n\times n$ 的矩阵，若 $(i,j)$ 为 $1$，则表示有一条 $i$ 到 $j$ 的边。那么，就可以直接矩阵快速幂优化了。朴素的时间复杂度为 $O(qn^3\log V)$。若将 $E^{2^i}$ 预处理出来，则可以做到 $O(qn^2\log V)$。