题解：AT_agc064_c [AGC064C] Erase and Divide Game

· · 题解

为何题解区无人画图。明明画图一看就懂。看了图感觉是水黑。

更咕咕咕的体验

不难想到从低位到高位建 01-trie，向左相当于保留偶数踢走奇数，向右相当于保留奇数踢走偶数。先从叶子节点走掉的人胜利。从叶子到根往上更新博弈状态即可。但是我们发现如果逐个插入数的话插入次数爆炸了，考虑以区间处理。但是又发现无法直接做到区间连续插入，插入的数分布是散的。

如何将区间连续处理是这道题比较难想的点。其实把树扭曲一下变成这样（图丑）：

就好了。为什么说好了，因为一层上面的编号是连续的，这样就可以打区间标记了。根为第 0 层，如果我们把第 k 层的 2^{k} 个点都建出来，打上空点、胜点、输点的标记，再往父亲合并。转为区间的话，每个区间记左端点、右端点和这个区间内点的类型。绿线是左儿子和右儿子的分割线，对于 0 \le x < 2^{k-1}，x 和 x + 2^{k-1} 合并。区间合并后还是区间，所以这样是可以层层推上去的。区间合并用双指针维护。

实现的时候注意，如果有区间跨过了绿线，要把它拆成左右两半。

::::info[代码]

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 10010;
int f[5][5],n,tot;
struct dat{
    int l,r,v;
}a[2 * N],b[4 * N],c[4 * N];
void init(){
    tot = 0;
}
void solve(){
    int L = 0,R = -1;
    scanf("%lld",&n);
    for(int i = 1,l,r; i <= n; i++){
        scanf("%lld%lld",&l,&r);
        if(R + 1 != l)a[++tot] = {R + 1,l - 1,0};
        a[++tot] = {l,r,1},L = l,R = r;
    }
    a[++tot] = {R + 1,(1ll << 60) - 1,0};
    for(int i = 60; i >= 1; i--){
        int mid = (1ll << (i - 1)),totb = 0,totc = 0;
        for(int j = 1; j <= tot; j++){
            if(a[j].l < mid)b[++totb] = {a[j].l,min(mid - 1,a[j].r),a[j].v};
            if(a[j].r >= mid)c[++totc] = {max(mid,a[j].l) - mid,a[j].r - mid,a[j].v};
        }
        L = 1,R = 1;int now = -1;tot = 0;
        while(L <= totb && R <= totc){
            a[++tot].l = now + 1;
            now = min(b[L].r,c[R].r);
            a[tot].r = now,a[tot].v = f[b[L].v][c[R].v];
            if(now == b[L].r)L++;
            else R++;
        }
    }
    if(a[1].v == 1)printf("Takahashi\n");
    else printf("Aoki\n");
}
signed main(){
    int T;
    for(int i = 0; i <= 2; i++)for(int j = 0; j <= 2; j++)f[i][j] = 1;
    f[0][0] = 0,f[1][1] = 2;
    scanf("%lld",&T);
    while(T--){
        init();solve();
    }
    return 0;
}

::::