【学习笔记】[AGC064C] Erase and Divide Game

有点难😅，看到比自己低一级的选手场切这道题就更绷不住了😇

考虑 从低到高位 建立 $\text{trie}$ 树，但是因为是对反串建立的，所以编号连续的点在 $\text{trie}$ 树上的位置是分散的😅

但是发现可以对$SG$值相同的一段区间一起转移，具体就是自底向上合并（编号减去$2^j$），每一层合并完了过后的区间数目都不会超过$n$（考虑端点的数目不会变）

让我想到了这道题 CF1864H Asterism Stream

大概也是分段转移

学了但是不会灵活运用，还是太菜了

复杂度$O(n\log V)$，非常优秀。

#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define fi first
#define se second
#define db double
#define ull unsigned long long
#define inf 0x3f3f3f3f
using namespace std;
const int N=2e4+5;
int T,n,m,cnt1,cnt2,cnt;
int to[3][3];
struct node{ll l,r;int v;
}a[N],b[N],c[N];
int get(int x,int y){return to[min(x,y)][max(x,y)];
}
int main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);cin>>T;to[0][0]=to[0][1]=to[0][2]=1,to[1][1]=0,to[1][2]=1,to[2][2]=2;while(T--){cin>>n;ll pre=0;cnt=0;for(int i=1;i<=n;i++){ll l,r;cin>>l>>r;if(pre<l)a[++cnt]={pre,l-1,2};a[++cnt]={l,r,1},pre=r+1;}if(pre<(1ll<<61))a[++cnt]={pre,(1ll<<61)-1,2};for(int i=60;i>=0;i--){cnt1=cnt2=0;for(int j=1;j<=cnt;j++){if(a[j].r<(1ll<<i)){b[++cnt1]=a[j];}else if(a[j].l>=(1ll<<i)){c[++cnt2]=a[j];}else{b[++cnt1]=a[j],b[cnt1].r=(1ll<<i)-1;c[++cnt2]=a[j],c[cnt2].l=1ll<<i;}}for(int j=1;j<=cnt2;j++)c[j].l-=1ll<<i,c[j].r-=1ll<<i;int p1=1,p2=1;cnt=0;while(p1<=cnt1&&p2<=cnt2){a[++cnt].l=b[p1].l,a[cnt].r=min(b[p1].r,c[p2].r),a[cnt].v=get(b[p1].v,c[p2].v);if(a[cnt].r==b[p1].r)p1++;else b[p1].l=a[cnt].r+1;if(a[cnt].r==c[p2].r)p2++;else c[p2].l=a[cnt].r+1;}}cout<<(a[1].v?"Takahashi":"Aoki")<<"\n";}
}