P7963 [NOIP2021] 棋局

给定 \(n\times m\) 的棋盘，连有横纵 \(2\) 种无向边，有 \(3\) 种类型的边：

1. 只允许按照这条边走 \(1\) 步
2. 允许继续走边权为 \(2\) 的边，但不允许改变方向
3. 允许继续走边权为 \(3\) 的边，可以改变方向

走到不同颜色等级 \(\leq\) 自己等级的棋子时可以吃掉棋子并停下，求先后放下 \(q\) 个棋子时每个棋子最多能走到的位置。

\(n\times m \leq 2\times 10^5,q\leq 10^5\)

感谢这篇博客让我 \(2\) 天做懂了这道神仙题。（写下这篇题解也算是对于 TA 的题解进行补充）

首先肯定会想到维护棋盘上格子的连通性，可以将所有 \(2\) 号道路连成的连续一条（行/列）维护在同一并查集内（所以需要 \(2\) 个并查集），将所有 \(3\) 号道路连成的连通块维护在同一并查集内。然而问题是放上棋子的过程就是断开连通性的过程，实在难以维护，想到的对策是离线所有询问，然后从后往前扫一遍，一边将连通性还原，一边统计答案。

吃子呢？首先 \(1,2\) 号道路好想，只用判断道路末端是否有棋子，若有则判断能否吃掉，如果能吃掉就计入答案。 \(3\) 号道路需要用一个数据结构来维护道路可抵达的所有棋子等级（其实是 \(2\) 个，分别维护 \(2\) 种颜色），然后查询某一连通块内指定颜色的比查询棋子等级小的元素个数（代码中的 \(query1\) ）。因为是维护每个并查集，所以还要涉及到合并操作，所以这里选择动态开点权值线段树的合并。

但是仅仅这样统计答案是不行的，比如

那么 \(1\) 号点就会被算 \(2\) 次。（既在 \(3\) 号并查集内，又在 \(2\) 号横向并查集内）

既然有重复的，那么就判重。利用 \(2\) 号边构成并查集内元素的连续性，可以在并查集中额外加入 \(maxn,minn\) 来得到这一段区间的最大值最小值，然后再额外创建 \(2\) 个线段树来维护横/竖的元素个数，然后可以通过查询区间和来得到被算重的元素个数（实际实现时通过前面提到的查询前缀函数 \(query1(r)-query1(l-1)\) 来实现区间和)。

然后是吃子的问题，所有的 \(1,2\) 道路的吃子都需要查询是否在 \(3\) 道路的吃子中，然而仅凭借等级是无法确定唯一棋子的，所以需要采取一种高级的离散化方法，让所有棋子的等级全部不同而不改变比大小的原则。具体的，让不同等级的棋子依然按照原顺序，而相同等级的棋子按照输入的先后顺序排序，这样之前的棋子就会比之后的棋子小，依然满足比大小的原则，而离散化之后可以通过唯一的等级确定某一棋子是否在线段树内。

最后是一些细节，比如通过用 \(e[i][j]\) 表示标号为 \(j\) 的棋子在 \(i\) 方向上的边权，用 \(val[i]\) 来记录 \(i\) 标号上的点是否有棋子，若有则为输入的顺序，线段树插入时多带一个 \(flag\) ，为 \(1\) 是插入，为 \(-1\) 是删除。