P9283

题目描述

• 在一个 $1$ 行 $n$ 列的棋盘上，有 $m$ 个棋子，第 $i$ 个棋子在从左往右第 $pos_i$ 列，颜色是 $col_i$。
• 现在 Alice 和 Bob 要轮流操作，操作如下：
  • 选中一个棋子以及它到右边下一个同色棋子（若不存在则到底）之间的所有棋子（包含左边不包含右边）。
  • 全部向前移动同一个距离，移动之后要保证棋子没有重叠并且棋子之间相对位置不变。
• Alice 先手，谁不能动谁就输了。

解题思路

先考虑只有一种棋子，那么每次就只移动一枚棋子。
那么我们把棋子之间的空位看成石子，那么题目就可以转化为：

• 有 $k$ 堆石子，Alice 和 Bob 轮流操作，每次可以选定一堆不是最右边的石子，取出若干石子，移动到右边相邻的堆里。
• Alice 先手，谁不能动谁就输了。

那么这就是阶梯 NIM 的模板题了，可以参考 P3480 [POI2009]KAM-Pebbles。
这里来粗略的讲一下阶梯 NIM 的做法。
为了方便起见，我们把顺序换一下，改成从第 $i$ 堆移动到第 $i-1$ 堆，移到第一堆结束。
正常的 NIM 是直接把石子扔掉，然而在阶梯 NIM 中，我们可以把奇数堆看成垃圾桶。

• 如果有人把偶数堆放到奇数堆，那么就相当于把石子扔掉了。
• 如果有人把奇数堆放到偶数堆，必胜者为了保持自己的必胜状态，一定可以把这些石子重新移到奇数堆里（第一堆是奇数堆）。

所以阶梯 NIM 就相当于只有偶数堆的普通 NIM，那么他的 SG 值就是偶数堆个数异或起来。

回到原来的问题上来，如果有多种颜色呢？
我们发现这和只有一种颜色的情况并没有很大的差别。
你在移动一种颜色的棋子时，并不会影响到其他颜色的棋子之间的间距。
所以我们只要对于每种颜色维护阶梯 NIM，也就数从右往左的偶数段长度异或和，最后异或起来即可。可以使用平衡树也可以离线加线段数维护。

示例代码

#include <bits/stdc++.h>
using namespace std;

constexpr int maxn = 2e5 + 10;

int n, m, q;
int b[maxn], tot;
int qry1[maxn], qry2[maxn], qry3[maxn];
int pos[maxn], col[maxn];
set<pair<int, int>> curpos;

#define lc (x << 1)
#define rc (x << 1 | 1)
#define mid (l + r >> 1)

struct segtree {
  struct node {
    int x, y, cnt;
  } t[maxn << 2];
  node merge(node a, node b) {
    if (a.cnt & 1) a.x ^= b.y, a.y ^= b.x;
    else a.x ^= b.x, a.y ^= b.y;
    a.cnt += b.cnt;
    return a;
  }
  void change(int x, int a, int b) {
    if (a != -1) t[x].x = a;
    if (b != -1) t[x].cnt = b;
  }
  void up(int x) {
    t[x] = merge(t[lc], t[rc]);
  }

  void update(int x, int l, int r, int q, int a, int b) {
    if (q < l || q > r) return;
    if (l == r) return change(x, a, b);
    update(lc, l, mid, q, a, b), update(rc, mid + 1, r, q, a, b);
    up(x);
  }

  void update(int q, int a, int b) {
    update(1, 1, tot, q, a, b);
  }
} t[5];

#undef lc
#undef rc
#undef mid

void insert(int pos, int col) {
  pos = lower_bound(b + 1, b + 1 + tot, pos) - b;
  auto it = curpos.upper_bound({pos, -1});
  if (it != curpos.end()) {
    t[it->second].update(it->first, b[it->first] - b[pos] - 1, 1);
  }
  int lst = 0;
  --it, lst = b[it->first];
  t[col].update(pos, b[pos] - lst - 1, 1);
  curpos.insert({pos, col});
}
void del(int pos) {
  pos = lower_bound(b + 1, b + 1 + tot, pos) - b;
  auto it = curpos.lower_bound({pos, 0});
  int col = it->second;
  int lst = b[prev(it)->first];
  auto it1 = next(it);
  if (it1 != curpos.end()) {
    t[it1->second].update(it1->first, b[it1->first] - lst - 1, 1);
  }
  t[col].update(it->first, 0, 0);
  curpos.erase(it);
}
int calc() {
  int ans = 0;
  for (int i = 0; i < 5; ++i) {
    if (t[i].t[1].cnt % 2 == 0) ans ^= t[i].t[1].y;
    else ans ^= t[i].t[1].x;
  }
  return ans;
}

int main() {
#ifndef LOCAL
  cin.tie(nullptr)->sync_with_stdio(false);
#endif
  cin >> n >> m;
  for (int i = 1; i <= m; ++i) cin >> pos[i] >> col[i], col[i]--;
  cin >> q;
  for (int i = 1; i <= q; ++i) {
    cin >> qry1[i];
    if (qry1[i] == 1) cin >> qry2[i] >> qry3[i], --qry3[i];
    else cin >> qry2[i];
  }
  for (int i = 1; i <= m; ++i) b[++tot] = pos[i];
  for (int i = 1; i <= q; ++i) if (qry1[i] == 1) b[++tot] = qry2[i];
  sort(b + 1, b + 1 + tot);
  curpos.insert({0, 0});
  tot = unique(b + 1, b + 1 + tot) - b - 1;
  for (int i = 1; i <= m; ++i) insert(pos[i], col[i]);
  for (int i = 1; i <= q; ++i) {
    if (qry1[i] == 1) insert(qry2[i], qry3[i]);
    else del(qry2[i]);
    cout << (calc() ? "Alice" : "Bob") << '\n';
  }
}