P12063 题解

· · 题解

首先把题意转化一下，就是说，我们要构造一个可能的棋局，然后模拟下棋的过程直到一方的棋盖装不下为止。

构造棋局是简单的——假设现在下的这一步要吃 k 颗棋子，那么在棋盘上找一块足够大的空位（不妨假设棋盘无限大）把这些棋子放下来即可，为了节省棋子我们尽可能让它堆成正方形。

但是还有个小问题：每一步的 a_i 实在太大了，无法存下所有棋子。因此我们必须把每个棋子的连通块转化成几个矩形的不交并的形式。

放完这些棋子之后，需要在旁边放一些异色的棋子把它围起来直到只剩一个空，这一步是简单的。

现在我们考虑下一步棋之后会发生什么。首先把它和与它相邻的棋子放进同一个连通块内（用并查集维护），然后我们需要判断有没有棋子被吃。

发现一步棋只会改变周围四个位置所在连通块的“气”，所以可以记录每个连通块的“气”的数量然后暴力修改。

我们先考虑周围的（异色）连通块是否被吃。如果它被吃了，那么需要把它删掉，这些棋子现在就被拿在手上。同时，开一个 vector 维护和它相邻的连通块和相邻的边数，删除时暴力修改周围所有的“气”即可。此时的“气”数量单调不增，所以不会出问题。

之后需要特判一种情况：放下棋子之后自己所在的位置被吃了，这样需要抛出异常。

同时，如果对方进行了一次打劫，那下一次不能当场吃回来。因此我们需要记录上一次落子的位置，如果它所在的连通块恰好只有一颗棋子并且它上一次恰好吃掉了一颗棋子那么不能立马吃回去。

现在我们可以维护棋局了，分析一下它的复杂度。

首先一开始构建的时候，可以保证只有 O(n) 个矩形——这是简单的。

定义势能函数为相邻的异色连通块的对数，一开始构造的时候也可以做到 O(n)。

每一步最多使势能 +4，修改气的代价为 O(1)，维护连通性的代价为 O(\alpha (n)))，一个块被吃掉的时候，暴力修改相邻块的气时，每个 O(1) 的修改消耗 1 点势能，而总势能是 O(n) 的。

然后你发现维护所有相邻的矩形这个东西很不好做，考虑把操作离线下来（在线也可以用二维线段树做到 O(n\log^2 n) 但过不了一点），先考虑横向相邻再考虑纵向相邻。那么肯定是把所有点按照纵坐标排序然后做扫描线，只需要在每个矩形加入和删除的时候查询相邻的位置即可。

在每个位置上开一个 set 维护当前位置的矩形，不难发现每次只需要修改左端点和右端点，中间的位置是没用的。

这里有一个细节：如果出现劫争，那么打劫的位置可能会把预处理时相邻的矩形对数卡到 O(n^2)，因此需要精细的实现去掉不可能同时出现的矩形对。

总复杂度是 O(n\log n) 的。（如果你觉得复杂度假了的话，考虑一下这条性质：如果一个位置在整个棋局中被不止一个矩形覆盖，那么只有第一个矩形的大小可能 >1\times 1。）

现在还不够，注意到我们吃掉的棋子还拿在手上，因此我们需要让棋手把棋子放进盒盖里。

显然我们需要维护三个东西：盒盖，桌面，以及棋钟。一个正确的提子流程是先把棋子放进盒盖里，然后按下棋钟。如果放不下棋子，那么就需要把多余的放在桌面上——这样最后对方举手，他就输了比赛。

桌面也可以视为无限大的二维平面。为了保证棋盘和桌面不发生穿模，必须限制棋盘的一个维度——这样只需对前面的东西进行一些小修改即可，并不困难。你也可以取宽度 W=\max\{a_i\}+O(1)，就没有问题了。

在桌面放下棋子时可以用上述的方法维护一个矩形。而为了提高空间利用率，棋盖是三维的。

把棋盖抽象成一棵树，它有 M 个节点，每次放棋子时棋子从根节点进入，选择一条路径尽可能往下滑，最后停止。这等价于：每次把棋放在根节点，然后选择一条路径往下推一格。

进一步对其进行抽象，我们认为这是一个从上到下放满整棵树的方案，第一次必须放根节点，后面每一步放的节点的父亲必须在它之前被占据。

现在我们令一个大小为 K 的树按照如下方式构造：

如果 K=1，则直接返回只有一个节点的树；

如果 K=2，直接返回一个只有根节点和其右儿子的树；

否则，新建一个节点，其左儿子递归构造 \lfloor\frac{K-1}{2}\rfloor 大小的树，右儿子递归构造 \lceil\frac{K-1}{2}\rceil 大小的树，返回这棵树。

这样，每一层（即深度相同）的树的大小极差为 1，也就是最多只有两种形态。

对树进行重链剖分，我们优先让棋子放在重儿子上。维护可行的重链的集合（不需要使用堆，队列即可），每次尽可能放满一条重链，放满之后把和它相邻的链也设为可行的重链。

然而重链的总数是 O(M) 的，无法接受。

现在我们取一个阈值 B，将最浅的大小全部 \le B 的一层拉出来，这一层的树至多有两种形态；对于每一种形态（设其大小为 S），用 O(S^2) 求出这里面放了 k=1...S 个节点时的状态（是否被放满，节点放置的方式）。这一步的复杂度是 O(B^2) 的。

对这样的东西进行缩点，这样树就只剩下了 O(\frac{M}{B}) 个节点，维护重链的复杂度就变成了 O(n+\frac{M}{B})。

平衡复杂度，令 B=\sqrt[3]M，总复杂度为 O(n+M^\frac{2}{3})。

最后按下棋钟，轮到对方继续棋局。

把这几个部分组合在一起，总复杂度 O(n\log n+M^\frac{2}{3})。

代码我没写。注意这道题细节非常多，很容易让复杂度像下面这份代码一样进化到 O(n)。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll n,m,s0,s1,a;
int main(){
    cin>>n>>m;
    for (int i=1;i<=n;++i){
        cin>>a;
        if (i&1){
            if ((s1+=a)>m){
                cout<<"White\n";return 0;
            }
        }
        else if ((s0+=a)>m){
            cout<<"Black\n";return 0;
        }
    }
    cout<<"Draw\n";
    return 0;
}