题解 CF494E 【Sharti】
Kewth
2020-03-15 11:39:19
套路题，棋盘博弈套矩形并。
---
棋盘博弈有个结论，每个可以翻的棋子可以认为是单独一个互不影响的子游戏。
换言之，对于每个染了色的棋子，只要考虑一个仅包含该棋子的游戏局面，求出该局面的 SG 值，然后将所有这样的 SG 值异或起来就是整个游戏的 SG 值。
---
考虑求出仅含一个染色棋子 $(x, y)$ 的 SG 值（以下部分没有证明）。
先忽略 $k$ 的限制。
有个被出烂的博弈结论：
- 假设棋盘是一个长条，那么在第 $x$ 个点的棋子其 SG 值为 $lowbit(x)$ 。
将这个结论推广到二维，加以归纳，可以发现忽略 $K$ 的前提下，棋子 $(x, y)$ 的 SG 值就是 $min(lowbit(x), lowbit(y))$ 。
而加上 $K$ 的限制后，第 $x$ 个点的棋子 SG 值为 $min(lowbit(x), lowbit(y), greatbit(k))$ 。
ps: 这里两个维度不是独立的，不能用 Nim 积（我第一眼把这题看成了 Boring Game 的翻版）
---
现在的问题是对于一个矩形并求出其 SG 值的异或和。
类似于矩形面积并，用扫描线 + 线段树进行维护。
注意到 $lowbit$ 都是 2 的整次幂，种类数是 $O(logN)$ 的，因此可以考虑在线段树中维护每个 $lowbit$ 的数量。
然后扫描线扫过一段时，同样求出这段区间每个 $lowbit$ 的数量，统计答案时只需要在两个维度 $O(log^2N)$ 分别枚举 $lowbit$ ，与 $greatbit(k)$ 一起取 min 即可算进答案。
至于求一段区间的 $lowbit$ 分布，首先转换为求一段前缀 $[0, n]$ 的 $lowbit$ 分布，数位 DP 一下或者通过逼近每个二进制位的方法可以 $O(logN)$ 实现，不在讨论重点。
---
时间复杂度 $O(mlog^2N)$ 。
空间复杂度 $O(mlogN)$ 。
参考实现：
```cpp
#include <cstdio>
#include <algorithm>
#include <cassert>
#define debug(...) fprintf(stderr, __VA_ARGS__)
typedef long long ll;
struct {
inline operator int () { int x; return scanf("%d", &x), x; }
inline operator ll () { ll x; return scanf("%lld", &x), x; }
} read;
const int maxn = 100005, maxk = 30;
struct Tree {
int cover, low[maxk];
} pool[maxn << 2];
#define self pool[now]
#define lt (now << 1)
#define rt (now << 1 | 1)
int pre[maxn][maxk];
void update(int now, int L, int R) {
if(self.cover)
for(int k = 0; k < maxk; k ++)
self.low[k] = pre[R][k] - pre[L - 1][k];
else if(L == R)
for(int k = 0; k < maxk; k ++)
self.low[k] = 0;
else
for(int k = 0; k < maxk; k ++)
self.low[k] = pool[lt].low[k] + pool[rt].low[k];
}
void modify(int now, int L, int R, int l, int r, int x) {
if(r < L or l > R) return;
if(l <= L and R <= r) return self.cover += x, update(now, L, R);
int M = (L + R) >> 1;
modify(lt, L, M, l, r, x);
modify(rt, M + 1, R, l, r, x);
update(now, L, R);
}
int get[maxk];
void getlow(int n) {
std::fill(get, get + maxk, 0);
for(int k = maxk - 1; k; k --) {
get[k - 1] += get[k] << 1;
if(n >> k & 1)
++ get[k - 1];
}
for(int k = 0; k < maxk; k ++)
if(n >> k & 1)
++ get[k];
}
struct Operation {
int l, r, t, o;
} op[maxn];
int tmp[maxn], tp;
int main() {
read.operator int();
int n = 0, m = read, K = read;
for(int k = 0; k < maxk + 1; k ++)
if((1 << k) > K) {
K = 1 << k >> 1;
break;
}
for(int i = 1; i <= m; i ++) {
int lx = read, ly = read;
int rx = read, ry = read;
op[i * 2 - 1] = {ly, ry, lx, 1};
op[i * 2] = {ly, ry, rx + 1, -1};
tmp[++ n] = ly - 1;
tmp[++ n] = ry;
}
std::sort(tmp + 1, tmp + n + 1);
n = int(std::unique(tmp + 1, tmp + n + 1) - tmp - 1);
for(int i = 1; i <= n; i ++) {
getlow(tmp[i]);
std::copy(get, get + maxk, pre[i]);
}
std::sort(op + 1, op + m * 2 + 1, [](Operation a, Operation b) {
return a.t < b.t;
});
int sg = 0;
for(int i = 1; i <= m * 2; i ++) {
int shit[maxk];
getlow(op[i].t - 1);
std::copy(get, get + maxk, shit);
getlow(op[i - 1].t - 1);
for(int k = 0; k < maxk; k ++)
shit[k] -= get[k];
for(int k1 = 0; k1 < maxk; k1 ++)
if(shit[k1] & 1)
for(int k2 = 0; k2 < maxk; k2 ++)
if(pool[1].low[k2] & 1)
sg ^= std::min({1 << k1, 1 << k2, K});
int l = int(std::lower_bound(tmp + 1, tmp + n + 1, op[i].l - 1) - tmp) + 1;
int r = int(std::lower_bound(tmp + 1, tmp + n + 1, op[i].r) - tmp);
modify(1, 1, n, l, r, op[i].o);
}
if(sg) puts("Hamed");
else puts("Malek");
}
```