【4.5】

典题，多次整体修改，把所有的 $a_i=x$ 改成 $a_i=y$ 。时间逆序。

朴素区间 DP 时间是 $O(n^3)$ 的，考虑如何枚举以达到优化。

优化思路类似于【智乃想考一道完全背包】。

较好的题。易得结论：每次将 $[ql,qr]$ 规定为特殊点，问 $[ql,qr]$ 中有多少个点的子树里没有特殊点。

分为两个子问题：

1. 求得每个点 $i$ 的子树内大于 $i$ 的最小编号和小于 $i$ 的最大编号，组成区间 $s_i$。
2. 问 $[ql,qr]$ 内有多少个 $i\in [ql,qr]$ 满足 $[ql,qr]\subset s_i$ 。

对于一（不完全）：

1. 启发式合并， $O(n{\log }^{2}n)$ 。
2. dfs 序上主席树区间查询，$O(n\log n)$ 。
3. max 线段树单点修改区间查询。从小到大枚举编号 $i$ ，使得前缀 $[1,i)$ 的点在dfs序上添加到线段树内，并区间查询最大值。时间复杂度 $O(n\log n)$ 。

对于二（不完全）：

对每个查询区间，问有多少个节点区间满足 $ul\le ql\le u\le qr\le ur$

3. cdq 分治，转化为离线三维偏序问题，时间复杂度 $O(n{\log }^{2}n)$
4. 容斥，等于 $|ul\le ql\le qr\le ur|-|ul\le u\le ql|-|qr\le u\le ur|$ ，二维数点（二位偏序）解决，时间复杂度 $O(n\log n)$

1+3解法：

AC代码：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=68612445

不考虑元素限制，相当于置换环上的交换。对于一个环 $l$ ，选择两个点进行交换（等价于数组上对应位置的元素交换），则拆分为两个环 $l1,l2(l1+l2=l)$ 。环长和不变，但是环数变多。

对于此题，相当于只能 01 元素才能交换。对于 01 环可以单独解决，对于 0 环和 1 环可以配对解决。

AC代码：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=68610245

此题关键是末端铺平，并利用 栈大小每次最多增大 1 来保证时间复杂度的线性。

题解：kjhhjki的博客

AC代码：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=68618210

这题的 trick 也比较典型：容斥原理求最大公约数为 k 的数对个数

大致思路就是，定义 $b_i$ 表示 $i$ 的倍数，对于 $i$ 的倍数两两配对进行 $gcd$ 运算的结果一定还是 $i$ 的倍数。定义 $f_i$ 表示 $gcd(a_x,a_y)=i$ 的对数，可以知道 ${\sum }_{k=1}^{i\times k\le n}{f}_{k\times i}=C_{b_i}^2$ 。容斥一下即可。

类似的题目：D. Counting Rhyme

小苯的逆序对

AC代码：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=68619463