不难想到从低位到高位建 01-trie，向左相当于保留偶数踢走奇数，向右相当于保留奇数踢走偶数。先从叶子节点走掉的人胜利。从叶子到根往上更新博弈状态即可。但是我们发现如果逐个插入数的话插入次数爆炸了，考虑以区间处理。但是又发现无法直接做到区间连续插入，插入的数分布是散的。
如何将区间连续处理是这道题比较难想的点。其实把树扭曲一下变成这样（图丑）：
就好了。为什么说好了，因为一层上面的编号是连续的，这样就可以打区间标记了。根为第 \(0\) 层，如果我们把第 \(k\) 层的 \(2^{k}\) 个点都建出来，打上空点、胜点、输点的标记，再往父亲合并。转为区间的话，每个区间记左端点、右端点和这个区间内点的类型。绿线是左儿子和右儿子的分割线，对于 \(0 \le x < 2^{k-1}\)，\(x\) 和 \(x + 2^{k-1}\) 合并。区间合并后还是区间，所以这样是可以层层推上去的。区间合并用双指针维护。
实现的时候注意，如果有区间跨过了绿线，要把它拆成左右两半。
点击查看代码
#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;
}