多重映射
典题，多次整体修改，把所有的 a i = x a_i=x ai=x 改成 a i = y a_i=y ai=y 。时间逆序。
圆
朴素区间 DP 时间是 O ( n 3 ) O(n^3) O(n3) 的，考虑如何枚举以达到优化。
优化思路类似于【智乃想考一道完全背包】。
外向树
较好的题。易得结论：每次将 [ q l , q r ] [ql, qr] [ql,qr] 规定为特殊点，问 [ q l , q r ] [ql, qr] [ql,qr] 中有多少个点的子树里没有特殊点。
分为两个子问题：
- 求得每个点 i i i 的子树内大于 i i i 的最小编号和小于 i i i 的最大编号，组成区间 s i s_i si。
- 问 [ q l , q r ] [ql, qr] [ql,qr] 内有多少个 i ∈ [ q l , q r ] i\in[ql, qr] i∈[ql,qr] 满足 [ q l , q r ] ⊂ s i [ql, qr]\subset s_i [ql,qr]⊂si 。
对于一（不完全）：
- 启发式合并， O ( n log 2 n ) O(n\log^2 n) O(nlog2n) 。
- dfs 序上主席树区间查询， O ( n log n ) O(n\log n) O(nlogn) 。
- max 线段树单点修改区间查询。从小到大枚举编号 i i i ，使得前缀 [ 1 , i ) [1, i) [1,i) 的点在dfs序上添加到线段树内，并区间查询最大值。时间复杂度 O ( n log n ) O(n\log n) O(nlogn) 。
对于二（不完全）：
对每个查询区间，问有多少个节点区间满足 u l ≤ q l ≤ u ≤ q r ≤ u r ul\leq ql\leq u\leq qr\leq ur ul≤ql≤u≤qr≤ur
- cdq 分治，转化为离线三维偏序问题，时间复杂度 O ( n log 2 n ) O(n\log^2 n) O(nlog2n)
- 容斥，等于 ∣ u l ≤ q l ≤ q r ≤ u r ∣ − ∣ u l ≤ u ≤ q l ∣ − ∣ q r ≤ u ≤ u r ∣ |ul\leq ql \leq qr\leq ur|-|ul\leq u\leq ql|-|qr\leq u\leq ur| ∣ul≤ql≤qr≤ur∣−∣ul≤u≤ql∣−∣qr≤u≤ur∣ ，二维数点（二位偏序）解决，时间复杂度 O ( n log n ) O(n\log n) O(nlogn)
1+3解法：
AC代码：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=68612445
小红的元素交换
不考虑元素限制，相当于置换环上的交换。对于一个环 l l l ，选择两个点进行交换（等价于数组上对应位置的元素交换），则拆分为两个环 l 1 , l 2 ( l 1 + l 2 = l ) l1, l2(l1+l2=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 b_i bi 表示 i i i 的倍数，对于 i i i 的倍数两两配对进行 g c d gcd gcd 运算的结果一定还是 i i i 的倍数。定义 f i f_i fi 表示 g c d ( a x , a y ) = i gcd(a_x, a_y)=i gcd(ax,ay)=i 的对数，可以知道 ∑ k = 1 i × k ≤ n f k × i = C b i 2 \sum_{k=1}^{i\times k \leq n} f_{k\times i}=C_{b_i}^2 ∑k=1i×k≤nfk×i=Cbi2 。容斥一下即可。
类似的题目：D. Counting Rhyme
AC代码：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=68619463