【题解】牛客网NOIP赛前集训营-提高组（第八场）

A染色

我们把染色操作倒过来考虑，染色的定义就变成了：如果当前格子未被染色，就染上对应的颜色，否则不进行操作。下面W表示白，R(l,r)表示把l到r的格子染成红，B类似。
比如：我们进行了操作R(3,4),B(1,5),R(2,4)，最终的格子是BRRRB。倒过来考虑也就是：先进行操作R(2,4)得到WRRRW，然后进行操作B(1,5)，我们发现中间三个格子已经被染色，于是我们只改变第一个和最后一个格子得到BRRRB。最后进行操作R(3,4)发现已经全部被染色，于是我们什么都不做。
这里，由于操作序列里的操作可以不选择任何格子，我们可以认为被染过色的格子左右两个格子是相邻的，并把被染过色的格子忽略。
这样转化之后，每个格子只能染一次色，且这个颜色已经被给定的颜色串唯一确定，染色就等价于从颜色串里删掉一段相等的字符，并把剩下的左右合并成新的颜色串。可以发现删掉的一定是极长的颜色相等的段，否则一定不优。因此，我们可以假设颜色串任意相邻两个字符不同。
考虑串BRBRBR，我们如果删掉任意一个不再两端的B，就变成了BRRBR或BRBRR，合并以后都是BRBR。如果删掉左边的B，串就变成了RBRBR。显然能产生RBRBR的操作也一定能产生BRBR，反之则不一定。因此我们可以发现，当能删中间字符时一定删中间字符，否则删两边字符。模拟这个过程即可。

B推箱子 

显然，每个矩形进入移动状态的时刻一定是整数，且进入移动状态就不会停下，因此我们只需要对每个矩形求出它进入移动状态的时刻。
考虑两个在 y 轴投影相交的矩形 , ，,, ，由于矩形不相交可以得到 ,, 。我们从 到 连边，长度 ,, ，容易发现这个图中从 s 出发到每个点的最短路就是每个矩形进入移动状态的时间。
然而这样建边复杂度是 O(n^2) 级别，无法接受。
我们考虑三个在 y 轴投影两两相交的矩形 ,, ，,,,，可以发现 ，因此我们不需要考虑 到 这条边。也就是，我们只考虑在 y 是某个确定的数时，“相邻“的两个矩形的连边就可以了。当 y 从负无穷到正无穷的过程中，使”相邻“关系变化的只有两种可能：新出现了一个下边界 =y 的矩形，或者一个上边界 =y 的矩形消失。对于前者，新增了两对相邻关系。对于后者，新增了一对。因此，边的数量其实是 O(n) 级别的。
我们在 y 不断增加的过程中用一个平衡树按照左边界维护每个矩形，支持加点、删点、查询某个点的前驱后继就能找到所有的边。这里，使用STL的set即可。对于其他语言选手，如果不会平衡树，你可以选择离散化之后线段树+二分。
最后，使用dijkstra算法求出从 s 出发的最短路即可，复杂度 O(n log n) 。

C Revue

由于任意时刻未被标记的格子一定是一个连续的区间，并且如果知道了这个区间就可以推算出先后手是谁。可以考虑使用区间dp在O(n^2)的时间内解决问题：
dp[l][r]表示若未被标记的区间为[l,r]，那么结束时游戏的得分是多少。
若是你的回合，那么dp[l][r]=max{dp[l+k][r], dp[l+k-1][r-1],…,dp[l][r-k]}
若是对手的回合，那么dp[l][r]=min{dp[l+k][r], dp[l+k-1][r-1],…,dp[l][r-k]}
注意到转移是O(K)的，状态数为O(N^2/K) （因为只有长度减一为K的倍数时才是一个合法的状态）
转移若使用单调队列，可以优化到O(1)，可以通过第三个子任务。
考虑二分答案游戏的得分是否能大于等于X。此时可以将游戏的目标改为，若最后的得分大于等于X则你胜，否则对手胜。于是序列中的权值可以改为0或1，0表示小于X，1表示大于等于X，这样我们只要判断你是否有策略可以使游戏最终得分为1。使用同样的dp。