AT_agc064_c [AGC064C] Erase and Divide Game 题解

先考虑所有 \(l_i=r_i\) 时怎么做，可以建出反向 Trie 树，问题转化为从根开始每次向左子树或右子树走，第一个拿到空子树的人输，直接在 Trie 上 dp 即可。

考虑从叶子层开始对每一层的点合并两个子树的 dp 值，发现每一层值相同的连续段是较少的。于是可以维护这些连续段，每次合并要将每个 \(f_i\) 与 \(f_{i+2^k}\) 合并，把连续段分成两部分双指针合并即可，时间复杂度 \(\mathcal O(N\log V)\)。

参考代码：

#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define rept(i,a,b) for(int i=a;i<b;++i)
#define drep(i,a,b) for(int i=a;i>=b;--i)
using namespace std;
struct node{
	ll l,r;int x;
};
node operator+(node x,node y){
	return {max(x.l,y.l),min(x.r,y.r),x.x!=-1||y.x!=-1?x.x!=1||y.x!=1:-1};
}
int T,n;
vector<node>s,s1,s2;
signed main(){
	scanf("%d",&T);
	while(T--){
		scanf("%d",&n); 
		ll l,r,ls=0;
		s.clear();
		rept(i,0,n){
			scanf("%lld%lld",&l,&r);
			if(ls<l)s.pb({ls,l,-1});
			s.pb({l,r+1,1}),ls=r+1;
		}
		s.pb({ls,1ll<<60,-1});
		drep(i,59,0){
			ll k=1ll<<i;
			s1.clear(),s2.clear();
			for(node i:s){
				if(i.r<=k)s1.pb(i);
				else if(i.l>=k)s2.pb({i.l-k,i.r-k,i.x});
				else s1.pb({i.l,k,i.x}),s2.pb({0,i.r-k,i.x});
			}
			s.clear();
			for(auto i=s1.begin(),j=s2.begin();i!=s1.end()&&j!=s2.end();){
				ll r=min(i->r,j->r);
				s.pb(*i+*j);
				if(i->r==r)i++;
				if(j->r==r)j++;
			}
		}
		puts(s[0].x?"Takahashi":"Aoki");
	}
	return 0;
}