AtCoder ARC207 总结
B
构造题。观察样例，发现 \(i\) 恰好三步到达 \(n-i\)，其他点都是两步到达，这使我们想到 \(n\) 为偶数时的解法：分成 \(\le n/2\) 和 \(>n/2\) 的两部分点，对于其中一部分，我们让一个点恰好两步到达恰好一个或两个点。而对于两部分之间的连边，我们让 \(n-i\) 连向 \(i\) 在它那一部分恰好两步到达的点，这样就使 \(n-i\) 恰好三步到达 \(i\)，且不影响其他点。
对于 \(n\) 为奇数时的情况，可以把 \(n\) 号点拎出来，其他 \(n-1\) 做偶数的情况，发现只要使 \(n\) 号点能两步内到达所有点即可满足条件。画两下发现只需将 \(n\) 号点连向所有奇数点即可。
对于 \(n=6\) 和 \(n=7\) 不能用上述方法构造，\(n=6\) 是 \(1,2,3,6,5,4\) 的环；\(n=7\) 是在环的基础上将 \(7\) 连向 \(1,3,5\)。当 \(n<6\) 时无解。
C
考虑到固定 \(r\)，那么只有 \(O(\log A)\) 个或值，且每种或值的左端点在一个区间 \([l_1,l_2]\) 内。
可以考虑对所有的 \(O(n\log A)\) 个 \((l_1,l_2,r)\) 按照或值排序，相同或值按 \(r\) 排序。
然后依次执行每个 \((l_1,l_2,r)\) 对答案的更新，即 \(dp_r\gets \max _{i\in [l_1,l_2]}dp_i+1\)。用线段树维护，复杂度 \(O(n\log n\log A)\)。
D
取出中心 \(4\times 4\) 的矩形然后跑暴力即可。
可以证明是对的，只要讨论 \(n,m\) 的不同奇偶性时的情况。