为方便表示时间复杂度，假设 n,qn,qn,q 同阶。
不带修：P1972
Difficulty：4.1 / Easy
定义 nexti\text{next}_inexti 为 iii 相同颜色的后继，即最小的 jjj 满足 j>i,Aj=Aij\gt i,A_j=A_ij>i,Aj =Ai 。显然可以 O(n)O(n)O(n) 求出。
定义 prei\text{pre}_iprei 为 iii 相同颜色的前继，即最大的 jjj 满足 j<i,Aj=Aij\lt i,A_j=A_ij<i,Aj =Ai 。显然可以 O(n)O(n)O(n) 求出。
考虑 lll 固定后，rrr 往右移动 111 格后会怎么样。显然：
* 如果 ArA_rAr 出现过了，答案不变。
* 如果 ArA_rAr 未出现过，答案 +1+1+1。
定义 cl,rc_{l,r}cl,r 为区间左端点为 lll，由 r−1r-1r−1 移动到 rrr 的贡献。
注意到 clc_lcl 与 cl+1c_{l+1}cl+1 的差距只在于 cl,lc_{l,l}cl,l 从 000 变成 111 与 AnextiA_{\text{next}_i}Anexti 从 111 变成 000 了。
我们可以主席树实现或者扫描线动态维护 ccc。
O(nlogn)O(n\log n)O(nlogn)。
record。
单点修：P1903
Difficulty：4.7 / Easy
考虑修改会产生什么影响。
显然，就是修改了 O(1)O(1)O(1) 个位置的 next\text{next}next。
而每次修改 nexti\text{next}_inexti 会给后面的查询中，区间与 [i,nexti][i,\text{next}_i][i,nexti ] 有左交集并且与 [prei,i][\text{pre}_i,i][prei ,i] 有右交集的答案产生 111 的影响。
哦，这下看懂了。
CDQ 分治即可。
O(nlog2n)O(n\log^2 n)O(nlog2n)，代码有时间再写。
区间修：P4690
Difficulty：4.8 / Easy
注意到修改 [l,r][l,r][l,r] 后，l≤i<rl\le i\lt rl≤i<r 的 next\text{next}next 会变成 i+1i+1i+1，其余的只有 prel\text{pre}_lprel 和 rrr 的 next\text{next}next 会改变。
假设已经修改了 [l1,r1][l_1,r_1][l1 ,r1 ] 并且没被动过，现在要修改 [l2,r2][l_2,r_2][l2 ,r2 ]。我们可以发现 [l1,r1)[l_1,r_1)[l1 ,r1 ) 与 [l2,r2)[l_2,r_2)[l2 ,r2 ) 的交集的 next\text{next}next 不会改变。
所以有一个结论，修改 qqq 次后 next\text{next}next 的总修改次数不超过 O(n+q)O(n+q)O(n+q)。
所以可以和上面一样，CDQ 分治即可。
O(nlog2n)O(n\log^2 n)O(nlog2n)，代码有时间再写。
