T1
题解
记 ppx−1=xp^{-1}_{p_x} = xppx −1 =x。
直接模拟题意的时间复杂度是 O(n5)O(n^5)O(n5)。对求 mex\mathrm{mex}mex 的方法稍加优化即可做到 O(n4)O(n^4)O(n4)。
对于特殊性质 A，立刻注意到 mex{p1…,pk}=k+1\operatorname{mex} \lbrace p_1 \dots, p_k \rbrace = k + 1mex{p1 …,pk }=k+1 当且仅当 ∀i,pi=i\forall i, p_i = i∀i,pi =i
，故答案全 000。
下面先给出正解。
首先，注意到 mex{pl,…,pr}\operatorname{mex} \lbrace p_l, \dots, p_r \rbracemex{pl ,…,pr } 不变，等价于 (l≤x≤r)=(l≤y≤r)(l \le x \le r) = (l \le y \le r)(l≤x≤r)=(l≤y≤r)
或 min{px,py}>mex{pl,…,pr}\min \lbrace p_x, p_y \rbrace > \operatorname{mex} \lbrace p_l, \dots, p_r \rbracemin{px ,py }>mex{pl ,…,pr }。充分性与必要性分别显然。
于是，(x,y)(x, y)(x,y) 是稳定化子，当且仅当不存在一个子段 {pl,…,pr}\lbrace p_l, \dots, p_r \rbrace{pl ,…,pr }
，使得 (l≤x≤r)≠(1≤y≤r)(l \le x \le r) \ne (1 \le y \le r)(l≤x≤r)=(1≤y≤r)
且 mex{pl,…,pr}≥min{px,py}\operatorname{mex} \lbrace p_l, \dots, p_r \rbrace \ge \min \lbrace p_x, p_y \rbracemex{pl ,…,pr }≥min{px ,py }
；换句话说，即 ∀1≤l<r≤n s.t. {1,…,min{px,py}−1}⊂{pl,…,pr}\forall 1 \le l < r \le n \text{ s.t. } \left \lbrace 1, \dots, \min \left \lbrace p_x, p_y \right \rbrace - 1 \right \rbrace \subset \left \lbrace p_l, \dots, p_r \right \rbrace∀1≤l<r≤n s.t. {1,…,min{px ,py }−1}⊂{pl ,…,pr }
，都成立 (1≤x≤r)=(1≤y≤r)(1 \le x \le r) = (1 \le y \le r)(1≤x≤r)=(1≤y≤r)。
进而想到枚举 v=min{px,py}v = \min \lbrace p_x, p_y \rbracev=min{px ,py }
。记 Lv=min1≤w≤vpw−1L_v = \min_{1 \le w \le v} p^{-1}_wLv =min1≤w≤v pw−1 ，Rv=max1≤w≤vpw−1R_v = \max_{1 \le w \le v} p^{-1}_wRv =max1≤w≤v pw−1 。由于上一段分析中 l,rl, rl,r
的任意性，可以发现 {x,y}={pv−1,pu−1}(u>v)\lbrace x, y \rbrace = \lbrace p^{-1}_v, p^{-1}_u \rbrace \pod{u > v}{x,y}={pv−1 ,pu−1 }(u>v)
是稳定化子，当且仅当 Lv<min{pv−1,pu−1}<max{pv−1,pu−1}<RvL_v < \min \lbrace p^{-1}_v, p^{-1}_u \rbrace < \max \lbrace p^{-1}_v, p^{-1}_u \rbrace < R_vLv <min{pv−1 ,pu−1 }<max{pv−1 ,pu−1 }<Rv 。
对应到最终的计数上，就是位置 pv−1p^{-1}_vpv−1 单点加 Rv−Lv+1−vR_v - L_v + 1 - vRv −Lv +1−v，Lv,…,RvL_v, \dots, R_vLv ,…,Rv 中所有 pi>vp_i > vpi >v 的位置 iii 加 111
。至此本题应不再有任何困难，一个树状数组即可解决问题。
时间复杂度 O(nlogn)O(n \log n)O(nlogn)，空间复杂度 O(n)O(n)O(n)。
部分与正解思路接近或能够进行一些有效转化的选手，应当可以立刻将时间复杂度优化到 O(n3)O(n^3)O(n3) 或 O(n2)O(n^2)O(n2)，获得一些子任务的分数。
对于排列随机的情形，应当只有 O(log2n)O(\log^2 n)O(log2n) 对本质不同的 (Lv,Rv)(L_v, R_v)(Lv ,Rv )。如果选手的时间复杂度与 ∑Rv−Lv\sum R_v - L_v∑Rv −Lv
有关，这一子任务可能有所帮助。
对于特殊性质 C, D，可以发现 l≠1l \ne 1l=1 的区间都是平凡的，只需考虑 l=1l = 1l=1 的情形，可能部分选手会推出较弱的转化。
示例代码
T2
题解
k=1k = 1k=1 时，显然：若 n=1n = 1n=1 则存在唯一的珍贵片段；否则不存在珍贵片段。
k=2k = 2k=2 时，分析顺序对可知：只有 {{s1,s2}∣s2−s1=1}\left \lbrace \left \lbrace s_1, s_2 \right \rbrace \mid s_2 - s_1 = 1 \right \rbrace{{s1 ,s2 }∣s2 −s1 =1}
有可能成为珍贵片段，而这些片段的确珍贵，构造是非常容易的。
k≥3k \ge 3k≥3
时，所有片段皆珍贵，构造性的思路见下。记 S={s1,…,sk},T={1,…,n}∖SS = \lbrace s_1, \dots, s_k \rbrace, T = \lbrace 1, \dots, n \rbrace \setminus SS={s1 ,…,sk },T={1,…,n}∖S
。注意到，对于 SSS 中的位置，必须令其单调上升；对于其余位置，令其单调下降是不劣的。可以考虑：对于 TTT
中的位置，能否令其要么无顺序前驱，要么无顺序后继？这个问题的答案是肯定的，只需令 as1,…,aska_{s_1}, \dots, a_{s_k}as1 ,…,ask
在值域上连续即可。于是构造呼之欲出：在 s2s_2s2 前令 TTT 中位置的取值尽可能大；在 s2s_2s2
后令其尽可能小即可。至此，我们对任意的 SSS，构造出了一个满足条件的 AAA。于是所有片段皆珍贵。
故答案为 {[n=1]k=1n−1k=2(nk)k=3\begin{cases} [n = 1] & k = 1 \\ n - 1 & k = 2 \\ \binom n k & k = 3 \\ \end{cases}⎩⎨⎧ [n=1]n−1(kn ) k=1k=2k=3 。
直接计算的时间复杂度可以轻松做到 O(k2)O(k^2)O(k2)，优化为 O(k)O(k)O(k)
的技巧无非应用 (nk)=n−k+1k(nk−1)\binom n k = \frac {n - k + 1} k \binom n {k - 1}(kn )=kn−k+1 (k−1n )。
示例代码
T3
题解
首先进一步压缩使得 ∀i,bi≠bi+1\forall i, b_i \ne b_{i + 1}∀i,bi =bi+1 。
先考察回文子串的形式。
对于一个子串 sl…srs_l \dots s_rsl …sr ，考察其跨过的压缩信息数 kkk。
首先注意到 2∣k2 \mid k2∣k 的子串不可能回文。
k=1k = 1k=1 的子串自然回文。
对于 k≥3k \ge 3k≥3 的子串，可以发现除头尾外的 k−2k - 2k−2 个压缩信息必定构成压缩信息意义上的长度为 k−2k - 2k−2 的回文串。所以，直接对压缩信息运行
Manacher 算法或哈希后二分，求出以每个位置为中心的最长回文半径，同时对 {a1,…,an}\lbrace a_1, \dots, a_n \rbrace{a1 ,…,an }
做前缀和，即可简单勾勒出以每条信息为中心的 k≥3k \ge 3k≥3 的回文子串之样貌。
于是，回文串被自然地分成了两类。
对于第一类，设该压缩信息为 sp+1…sn−q=cos_{p + 1} \dots s_{n - q} = c^osp+1 …sn−q =co，则对答案的贡献为
∑l=1m∑r=1m∑x=1o∑y=1o[l≤p+x≤(n−q+1)−y≤r]=∑x=1o∑y=1o−l+1(p+x)(q+y)=∑x=1o∑y=1o−l+1(pq+px+qy+xy)=(∑x=1o∑y=1o−l+11)pq+(∑t=1ot(o−t+1))(p+q)+(∑x=1o∑y=1o−l+1xy)=(o+12)pq+((o+1)(o+12)−∑t=1ot2)(p+q)+(o+34)\begin{aligned} & \sum_{l = 1}^m \sum_{r = 1}^m \sum_{x = 1}^o \sum_{y = 1}^o [l \le p + x \le (n - q +
1) - y \le r] \\ = & \sum_{x = 1}^o \sum_{y = 1}^{o - l + 1} (p + x) (q + y) \\ = & \sum_{x = 1}^o \sum_{y = 1}^{o - l + 1} (pq + px + qy + xy) \\ = & \left(\sum_{x = 1}^o \sum_{y = 1}^{o - l + 1} 1 \right) pq + \left(\sum_{t = 1}^o t (o - t + 1) \right)(p + q) + \left( \sum_{x = 1}^o \sum_{y =
1}^{o - l + 1} xy \right) \\ = & \binom {o + 1} 2 pq + \left( (o + 1) \binom {o + 1} 2 - \sum_{t = 1}^o t^2 \right) (p + q) + \binom {o + 3} 4 \\ \end{aligned} ==== l=1∑m r=1∑m x=1∑o y=1∑o [l≤p+x≤(n−q+1)−y≤r]x=1∑o y=1∑o−l+1 (p+x)(q+y)x=1∑o y=1∑o−l+1 (pq+px+qy+xy)(x=1∑o y=1∑o−l+1 1)pq+(t=1∑o
t(o−t+1))(p+q)+(x=1∑o y=1∑o−l+1 xy)(2o+1 )pq+((o+1)(2o+1 )−t=1∑o t2)(p+q)+(4o+3 )
而 ∑k=1nk2=n(n+1)(2n+1)6\sum_{k = 1}^n k^2 = \frac{n (n + 1) (2n + 1)} 6∑k=1n k2=6n(n+1)(2n+1) 是经典的，于是上式可 O(1)O(1)O(1) 计算。
对于第二类，同理上类，贡献无非以下形式：
∑t=0k−1(l−t)(r−t)=klr−(k2)(l+r)+∑t=0k−1t2\begin{aligned} & \sum_{t = 0}^{k - 1} (l - t) (r - t) \\ = & klr - \binom k 2 (l + r) + \sum_{t = 0}^{k - 1} t^2 \\ \end{aligned} = t=0∑k−1 (l−t)(r−t)klr−(2k )(l+r)+t=0∑k−1 t2
亦可 O(1)O(1)O(1) 计算。
若使用 Manacher 算法，总时空复杂度皆为 O(n)O(n)O(n)。
示例代码
T4
题解
记 C=max{ai,bj}C = \max \lbrace a_i, b_j \rbraceC=max{ai ,bj }。记全体质数构成的集合为 P\mathbb PP。
正解之思路是直接的：
∑t∈Af(s,t)=∑t∈Atgcd(s,t)=∑x∣s1x∑x∣t∈At[gcd(s,t)=x]=∑x∣s1x∑x∣t∈At∑xy∣gcd(s,t)μ(y)=∑xy∣sμ(y)x∑xy∣t∈At=∑m∣s(∑y∣myμ(y)m)(∑m∣t∈At)=∑m∣s(∑y∣myμ(y))(1m∑m∣t∈At)≜∑m∣sf(m)g(m)m\begin{aligned} & \sum_{t \in A} f(s, t) \\ = & \sum_{t \in A} \frac t {\gcd(s, t)} \\ = & \sum_{x \mid s} \frac 1 x \sum_{x \mid t
\in A} t \left[ \gcd(s, t) = x \right] \\ = & \sum_{x \mid s} \frac 1 x \sum_{x \mid t \in A} t \sum_{xy \mid \gcd(s, t)} \mu(y) \\ = & \sum_{xy \mid s} \frac {\mu(y)} x \sum_{xy \mid t \in A} t \\ = & \sum_{m \mid s} \left( \sum_{y \mid m} \frac {y \mu(y)} m \right) \left( \sum_{m \mid t \in A} t
\right) \\ = & \sum_{m \mid s} \left( \sum_{y \mid m} y \mu(y) \right) \left( \frac 1 m \sum_{m \mid t \in A} t \right) \\ \triangleq & \sum_{m \mid s} f(m) \frac {g(m)} m \\ \end{aligned} ======≜ t∈A∑ f(s,t)t∈A∑ gcd(s,t)t x∣s∑ x1 x∣t∈A∑ t[gcd(s,t)=x]x∣s∑ x1 x∣t∈A∑ txy∣gcd(s,t)∑ μ(y)xy∣s∑ xμ(y)
xy∣t∈A∑ tm∣s∑ y∣m∑ myμ(y) m∣t∈A∑ t m∣s∑ y∣m∑ yμ(y) m1 m∣t∈A∑ t m∣s∑ f(m)mg(m)
其中，μ(⋅)\mu(\cdot)μ(⋅) 可以线性筛出；f(⋅),g(⋅)f(\cdot), g(\cdot)f(⋅),g(⋅) 及最后一个 ∑\sum∑ 均为 Dirichlet
前缀和或后缀和的形式，可以 O(CloglogC)O(C \log \log C)O(CloglogC) 时间 O(C)O(C)O(C) 空间求出。
于是，在 O(CloglogC)O(C \log \log C)O(CloglogC) 时间 O(C)O(C)O(C) 空间的预处理后，可以单次 O(1)O(1)O(1) 地回答询问。总时间复杂度 O(n+CloglogC)O(n + C \log \log C)O(n+CloglogC)
，总空间复杂度 O(C)O(C)O(C)。
下就部分子任务给出简要思路。
对于测试点 1,21, 21,2，直接或在对 AAA 中 1,…,C1, \dots, C1,…,C 计数后，模拟题意即可。
对于特殊性质 A, C，注意到以下事实后，对每个质数 ppp 记录 ∑[p∣ai]\sum [p \mid a_i]∑[p∣ai ] 与 ∑ai[p∣ai]\sum a_i [p \mid a_i]∑ai [p∣ai ]，进而求出答案并无任何困难。
f(x,y)={yx⊥y(1)1y∣x(2)yxx∣y(3)rx=pq,y=qr,(p,q,r∈P),p≠r(4)f(x, y) = \begin{cases} y & x \perp y & \pod 1 \\ 1 & y \mid x & \pod 2 \\ \frac y x & x \mid y & \pod 3 \\ r & x = pq, y = qr, (p, q, r \in \mathbb P), p \ne r & \pod 4 \\ \end{cases} f(x,y)=⎩⎨⎧ y1xy r x⊥yy∣xx∣yx=pq,y=qr,(p,q,r∈P),p=r
(1)(2)(3)(4)
对于特殊性质 B1，其思路与正解几乎全同，无非在推导过程中将一些 ∑t∈A\sum_{t \in A}∑t∈A 改为 ∑t=1n\sum_{t = 1}^n∑t=1n 而已。
示例代码
