- P9981
- 一开始我是直接想到了暴力做 hash + 倍增的，带两个 \(\log\)
- 对于DAG来言，我们通过一次拓扑排序按照最长路分层，按层从小到大遍历，每层的每个点赋予一个排名，往下一次更新答案就是按（边权，排名）的双关键字排序即可。\(O(N \log_{N})\)
- P10137
- 对于交叉路口而言，可以定义 \(f(x,y,0/1)\) 表示当前的坐标以及时间的奇偶性，基于这个我们可以进行一个倍增，但是很显然会爆。
- 进一步发现，若把 横线和竖线拆开来看
- 我们先讨论一下横线的情况，（竖线也是同理的）（先对横线按照 \(y\) 坐标排序）
- 我们考虑计算 这条横线转了两次方向后会到哪条横线上，我们发现这与另一个坐标 \(x\) 无关只与 \(y\) 坐标有关，意思就是它是能和竖线拆开来考虑的
- 定义 \(f_{i,j}\) 表示第 \(i\) 条横线转了 \(2^j\) 次两次方向到了哪条横线上。
易得
- \(f_{i,0} = f_{i+1,0} (dis \equiv 0\mod 2 )\)
- \(f_{i,0} = i + 1 (dis \equiv 1 \mod 2)\)
- 按照普通倍增转移即可
- 最后对于查询，我们先找到最近的交叉路口，再用横竖线的 \(f\) 数组来算出它到了哪里横竖线同时转移同时加步数,如果步数不够了就不走这个 \(2^j\) 次步。，多了的步数简单判一下即可
- p9980
就是从后往前，每个记下方案的奇偶性，去弄就行了，\(O(N^3)\) 的做法比较简单，后面再优化的话好像就是矩阵逆之类的了晚点我看下回放讲的是哪种做法
