A
题意：给定 \(n, a_{1\sim n}, b_{1\sim n}\)，两个点 \(i,j\) 之间有连边当且仅当 \(a_i - a_j\le i - j \le b_i - b_j\) 或 \(a_j - a_i\le j - i\le b_j - b_i\)，求图中连通块数量。
\(1\le n\le 10^6\)
考虑条件 \(a_i - a_j\le i - j \le b_i - b_j\) 相当于 \(a_i - i\le a_j - j\) 并且 \(i - b_i\le j - b_j\)。
令 \(x_i = a_i - i,\ y_i = b_i - i\)，那么满足 \(x_i\le x_j\) 且 \(y_i\le y_j\) 的两个点 \(i, j\) 连边。
将所有点按 \(x_i\) 从小到大排序，用一个栈表示目前所有连通块的最小的 \(y\) 值，每次加入一个点更新即可。
B
题意：平面上有 \(n\) 个点，请你确定 \(k\) 条互相平行的直线，满足每个点至少在一条直线上，并且每条直线上至少有 \(2\) 个点。数据保证至少有一个解。
\(2\le n\le 4\times 10^4, \ 1\le k\le \min(50, \frac n2)\)
鸽巢原理，考虑前 \(k + 1\) 个点至少有两个点被分配到同一条直线上。枚举这两个点，即可确定直线的斜率，然后 \(O(n)\) 判定，时间 \(O(nk^2)\)。
有更优的做法。考虑处理出这 \(n\) 个的上 / 下凸包，那么直线的斜率一定取自于凸包上相邻两点的斜率，这样只需要枚举 \(O(k)\) 次了。
C
题意：给定 \(n\)，计数有多少个严格单调递增，值域在 \([1, 2^n)\) 的序列 \((a_1, a_2, \dots, a_m)\) 满足不存在位置 \(i(1\le i\le m - 2)\) 满足 \(a_i \oplus a_{i + 1} \oplus a_{i + 2} \not = 0\)，答案对 \(998244353\) 取模。
\(1\le n\le 2\times 10^7\)
考虑按第 \(n\) 位来分类。第 \(n\) 位为 \(1\) 的数一定满足条件，第 \(n\) 位为 \(0\) 的数可以划分子问题，所以可以按分界线处来容斥。
设 \(f[i]\) 表示位数为 \(i\) 且最后一个数的第 \(i\) 位为 \(1\) 的方案数，总方案数为 $f[i - 1]\cdot $
标签：直线,le,题意,10,37,位为,CSP,模拟,个点 From： https://www.cnblogs.com/Sktn0089/p/18464475