无穷大的二位网格平面上, $(0, 0)$ 处有一个障碍物. 现在有一个由 R, L, U, D 组成的长度为 $n$ 的操作序列和一个机器人. 操作序列表示控制机器人如何走(上下左右), 如果机器人的下一步是障碍物(即原点), 那么他不行动. 现在有 $Q$ 次询问, 每次询问给出机器人的起点, 问终点. 保证机器人不在 $(0, 0)$.

$1 \le n, q \le 3 \cdot 10^5$

jyz nb!

不要被"一个“给误导了, 把所有询问都放在图上, 然后同时开始执行操作, 想象一下, 是不是有种"背景在动"的感觉? 没错, 这就是 “相对运动”. 与其操作 $Q$ 个机器人, 不如反向操作一个障碍物. 假设在障碍物移动的过程中, 没有碰到任何机器人, 那么障碍物移动的轨迹反一下, 就是所有机器人移动的轨迹了. 障碍物移动的轨迹可以通过二位向量前缀和求得. 统计答案每个机器人起点对它做差即可. 于是, 对于障碍物移动过程中碰到的机器人, 我们想办法改变机器人的起点, 使得其终点不变, 但不再碰见障碍物. 这是好办的, 因为障碍物碰见机器人了的话, 就证明机器人在这个时候会去撞障碍物(相对运动), 那么让机器人"后退"一步, 再执行这个操作, 后续操作是一模一样的. 所以做法就是, 相对运动移动障碍物, 碰到机器人就"推"一下. 需要注意的是, 障碍物移动一下最多推 $n$ 个机器人, 但是这些机器人在后续操作中就等价了, 所以只用搞一个代表出来就行, 用并查集合并一下即可.

(zzs讲课没听, vp遭殃)

打牛客发现完全不会概率期望, 高中课本上的东西就是个屑, 大概率徐积限自己也不清楚就乱教. 冥思苦想, 用自己的方式理解了一波, 记录一下.

太弱小了! 没有力量!

太弱小了! 没有力量!

有 $n$ 个长度为 $10^9$ 的01串, 一个排在一行. 需要删去一些01串(行), 使得相邻两行中, 至少存在一列, 这一位上两个都是1.

01串由 m 个区间的形式给出, 三元组 $(i, l, r)$ 表示第 $i$ 个01串中, $[l,r]$ 区间上都是1.

求一个删除次数最少的方案.

$1 \le n, m \le 3 \cdot 10^5$

显然dp. 印象里早年在洛谷某次月赛做到过相似的题, 也是一行一行dp, 但是我忘记了, 有空回去补补.

设 $dp(i)$ 表示前 $i$ 行, 选第 $i$ 行, 能够留下来的最多多少行. 转移显然从能够相邻的前面的状态转移.

问题就在于, 如何快速知道, 哪些行可以和这一行相邻. 注意到第 $i$ 行的1是若干段连续的区间, 如果某一行和这些区间有交集, 那么就可以转移. 也就是说, 我们需要一个区间查询的操作. 这里就上线段树, 开一个大小为 $10^9$ 的线段树, 记录哪些点存在哪些行之类的信息. 做完一行时如果我们把当前行上1的区间加上当前行, 这样区间查询一下, 就知道可以从哪里转移了. 由于我们需要取最大值, 那么更小的点永远不会是决策点, 所以可以在点中记录 $dp(j)$ 的最大值, 同时记录决策点(因为需要方案), 然后区间查询最大值, 可以很方便地转移.

不会暴力, 分块好难.