[NOIP2021] 棋局

快跑，这是一道大模拟！

[NOIP2021] 棋局 - 洛谷P7963

标签

线段树，并查集

加入一个棋子，相当于将一个连通块分裂，这是不好办的。不妨倒过来，先把所有棋子加进去，再合并连通块。

三种道路中，只有第三种最不好处理，需要同时维护空格与棋子。为了查询当前棋子能吃掉哪些，需要开两棵线段树，表示两种颜色来维护等级，合并时使用线段树合并。因为两个连通块可能可以接触到同一个棋子，所以合并时需十分谨慎，每个棋子都要开一个位置。

对于第二种道路，到达的一定是一条横线加一条竖线，且棋子只能出现在端点（至多 \(4\) 个），使用线段树（并查集）维护每一行、每一列的连续段（棋子消失表示合并）算出能到达的棋子数。

关键在于去重，如何去掉两类的交集？

我们给每个格子编两个号，两个编号都由两个关键字组成，一个先按行，后按列；另一个先按列，后按行。那么第二类道路能到达的点中可以演变成两端区间（横着一个，竖着一个），在第三类道路中用线段树维护这两种编号即可。而对于棋子，因为最多四个，暴力查询就可以了（使用启发式合并即可）。

第一类道路至多只能到达四个格子，也是暴力判即可。

时间复杂度是巨大常数的单 \(\log\) 。

为了方便，我把所有地方都开了线段树，导致了更大的常数。。。

因为要开很多棵线段树，合并时可能还有一些去重的问题，空格和棋子不能混在一起。。。所以极为 shit，费时 \(2 days\) 终于通过。