A - Reachable Towns
给定平面上 (n) 个点 ((x_i, y_i)) ，其中 (x_i, y_i) 分别是 (1, 2, cdots, n) 的排列
定义点 (i) 可以到达点 (j) 当且仅当 (x_i<x_j, y_i<y_j) 或 (x_i>x_j, y_i>y_j)
对于每个 (1leq kleq n) ，求出从 (k) 出发能走到多少个点
(nleq2 imes10^5)
如果只有条件 (x_i<x_j, y_i<y_j) ，按 (x_i) 考虑，维护 (y_i) 降序的单调栈，用并查集维护能走到的点的集合
对于条件 (x_i>x_j, y_i>y_j) 再扫一遍即可
时间复杂度 (O(n))
B - Sum is Multiple
给定整数 (n) ，找到最小的正整数 (k) 满足 (n|frac {k(k+1)}2)
(nleq10^{15})
可得 (2n|k(k+1)) ，而 (k) 与 (k+1) 互质
由于在 (10^{15}) 范围内一个数最多有 (13) 个不同的质因数，考虑枚举 (2n) 的每个质因数的若干次幂出现在 (k) 还是 (k+1)
容易发现这是若干个同余方程，使用 CRT 即可
时间复杂度 (O(2^{omega(n)}omega(n)log n))
C - Moving Pieces
有一个 (n imes m) 的网格，每个点上可以是空地、障碍或棋子
你每次可以执行以下操作：选择一个棋子，将其往下或往右移动一格，要求不能移出棋盘，且目的地不能是障碍或已经存在一个棋子
- (n, mleq50)
- 保证棋子个数 (leq100)
将棋子看做左部点，所有非障碍位置看做右部点，做带权二分图匹配即可
D - Keep Distances
给定数轴上 (n) 个升序的不同位置 (X_i) 和一个常数 (k)
有 (q) 次询问，每次给出 ([l, r]) ，定义一个集合 (S) 是合法的当且仅当：
- 集合 (S) 中的每个元素均为 (X_l, X_{l+1}, cdots, X_r) 之一
- 对于集合中任意两个不同元素 (x, y) ，满足 (|x-y|ge K)
- 满足上述两个条件的前提下，集合 (S) 的大小尽量大
你需要对于该询问找到所有合法集合的并的大小
- (n, qleq2 imes10^5; Kleq10^9)
- (1leq X_1<X_2<cdots<X_nleq10^9)
对于单次询问 ([l, r]) ，记 (cnt) 为合法集合的大小， (f(i)) 是满足区间 ([l, f(i)]) 中合法集合大小为 (i) 的最小位置， (g_i) 是满足区间 ([g(i), r]) 中合法集合大小为 (i) 的最大位置
不难发现答案等于 (displaystylesum_{i=1}^{cnt}g(i)-f(cnt-i+1)+1)
若 (g(i)<f(cnt-i+1)) ，可以反证得到合法集合大小小于 (cnt)
而对于开区间 ([f(cnt-i+1), g(i)]) 中的元素 (x) ，可以将位置 (f(cnt-i+1)) 和 (g(i)) 替换成 (x) 得到一个新的合法集合
因此可以将求和拆开，用倍增维护集合，时空复杂度 (O(nlog n))