模拟赛放了道 *3500，结果全场都切了，非常恐怖。
首先考虑怎么样的树是合法的，打个表发现 SG 函数值为 \(\sum_{d}2^d·(\text{深度为 d 的点个数}\bmod 2)\)，换句话说后手必胜当且仅当每种深度的点数都是偶数。
于是实际上我们只用建出虚树之后树上差分一下求出每个点被覆盖的情况，进而能够求出答案。
考虑如果我们要建出虚树需要实现哪些功能：
-
快速求一个点的深度，发现很傻，\((x,y)\) 的深度实际上就是 \(x+y\)。
-
快速求两个点的 LCA。由于给定的树是一个分形，所以考虑查询的两个点在当前分形（假设大小为 \(2^k\)）三个部分中的哪一个，如果在同一个部分则进入那一个部分继续递归，否则 LCA 显然在左上角那个部分中，把右上角的点提到 \((0,2^{k-1}-1)\)，把左下角的点提到 \((2^{k-1}-1,0)\)，然后继续递归即可。
-
比较两个点的 DFS 序，如果两者存在祖先后代关系那么深度较小的那个靠前，否则同理在分形上跑一下。
由于比较 DFS 序需要一个 \(\log\)，再加上排序一个 \(\log\)，总共是 2log，可以通过。
所以这题实际上是一个巨大缝合怪，配不上其 *3500 的难度（
具体实现的时候写得比较累赘，可能和上面说得不太一样，看看就好。
const int MAXN=4e5;
int n,lc[MAXN+5];pii p[MAXN+5],pt[MAXN+5];
map<pii,int>id;int idcnt=0;
int getid(int x,int y){
if(id[mp(x,y)])return id[mp(x,y)];
else return id[mp(x,y)]=++idcnt,pt[idcnt]=mp(x,y),idcnt;
}
pii getlca(int xa,int ya,int xb,int yb,int d){
if(!d)return mp(0,0);
int lim=(1<<d-1);
if(xa<lim&&ya<lim&&xb<lim&&yb<lim)return getlca(xa,ya,xb,yb,d-1);
else if(xa>=lim&&xb>=lim){
pii p=getlca(xa-lim,ya,xb-lim,yb,d-1);
return mp(p.fi+lim,p.se);
}else if(ya>=lim&&yb>=lim){
pii p=getlca(xa,ya-lim,xb,yb-lim,d-1);
return mp(p.fi,p.se+lim);
}else if((xa>=lim||ya>=lim)&&(xb>=lim||yb>=lim))return mp(0,0);
else{
if(xb<lim&&yb<lim)swap(xa,xb),swap(ya,yb);
if(xb>=lim)return getlca(xa,ya,lim-1,0,d-1);
else return getlca(xa,ya,0,lim-1,d-1);
}
}
bool getcmp(int xa,int ya,int xb,int yb,int d){
if(!d)return 0;
int lim=(1<<d-1);
if(xa<lim&&ya<lim&&xb<lim&&yb<lim)return getcmp(xa,ya,xb,yb,d-1);
else if(xa>=lim&&xb>=lim)return getcmp(xa-lim,ya,xb-lim,yb,d-1);
else if(ya>=lim&&yb>=lim)return getcmp(xa,ya-lim,xb,yb-lim,d-1);
else{
int ida=((xa>=lim)?0:((ya>=lim)?2:1));
int idb=((xb>=lim)?0:((yb>=lim)?2:1));
return ida<idb;
}
}
vector<int>g[MAXN+5];int rt;
int build(vector<tuple<int,int,int> >v,int cx,int cy,int d){
if(v.empty())return 0;
if(v.size()==1)return get<2>(v[0]);int lim=1<<d-1;
vector<tuple<int,int,int> >A,L,R;
for(tuple<int,int,int>t:v){
if(get<0>(t)>=lim)L.pb(mt(get<0>(t)-lim,get<1>(t),get<2>(t)));
else if(get<1>(t)>=lim)R.pb(mt(get<0>(t),get<1>(t)-lim,get<2>(t)));
else A.pb(t);
}
if(L.empty()&&R.empty())return build(A,cx,cy,d-1);
else if(A.empty()&&R.empty())return build(L,cx+lim,cy,d-1);
else if(A.empty()&&L.empty())return build(R,cx,cy+lim,d-1);
else{
int a=build(A,cx,cy,d-1),l=build(L,cx+lim,cy,d-1),r=build(R,cx,cy+lim,d-1);
if(l){pii mx=mp(-1,0);for(auto t:A)if(get<1>(t)==0)chkmax(mx,mp(get<0>(t),get<2>(t)));g[mx.se].pb(l);}
if(r){pii mx=mp(-1,0);for(auto t:A)if(get<0>(t)==0)chkmax(mx,mp(get<1>(t),get<2>(t)));g[mx.se].pb(r);}
return a;
}
}
int mark[MAXN+5],vis[MAXN+5],fa[MAXN+5];
void dfs(int x,int f){fa[x]=f;for(int y:g[x])dfs(y,x),mark[x]+=mark[y];}
map<int,int>dif;
void add(int l,int r){dif[l]^=1;dif[r+1]^=1;}
bool cmp(int x,int y){
if(x==0)return 0;
pii lca=getlca(pt[x].fi,pt[x].se,pt[y].fi,pt[y].se,30);
if(lca==pt[x])return 1;if(lca==pt[y])return 0;
return getcmp(pt[x].fi,pt[x].se,pt[y].fi,pt[y].se,30);
}
int main(){
scanf("%d",&n);vector<int>v;map<int,int>in;
for(int i=1,xa,ya,xb,yb;i<=n;i++){
scanf("%d%d%d%d",&xa,&ya,&xb,&yb);
p[i].fi=getid(xa,ya);p[i].se=getid(xb,yb);
pii pp=getlca(xa,ya,xb,yb,30);lc[i]=getid(pp.fi,pp.se);
if(!in[p[i].fi])v.pb(p[i].fi),in[p[i].fi]=1;
if(!in[p[i].se])v.pb(p[i].se),in[p[i].se]=1;
}
sort(v.begin(),v.end(),cmp);
for(int i=1;i<v.size();i++){
pii pp=getlca(pt[v[i-1]].fi,pt[v[i-1]].se,pt[v[i]].fi,pt[v[i]].se,30);
getid(pp.fi,pp.se);
}
vector<tuple<int,int,int> >vec;
for(int i=1;i<=idcnt;i++)vec.pb(mt(pt[i].fi,pt[i].se,i));
rt=build(vec,0,0,30);
for(int i=1;i<=n;i++)vis[lc[i]]=1,mark[p[i].fi]++,mark[p[i].se]++,mark[lc[i]]-=2;
dfs(rt,0);
for(int i=1;i<=idcnt;i++){
if(vis[i]||mark[i])add(pt[i].fi+pt[i].se,pt[i].fi+pt[i].se);
if(mark[i])add(pt[fa[i]].fi+pt[fa[i]].se+1,pt[i].fi+pt[i].se-1);
}
int sum=0;
for(pii pp:dif)if(pp.se)sum++;
if(!sum)puts("0");
else{
sum--;
if(!dif[0])++sum;
printf("%d\n",sum);
}
return 0;
}
/*
*#*#############
#.*.#.#.#.#.#.#.
#*..##..##..##..
#...*...#...#...
####....####....
#.#.....#.#.....
##......##......
#.......#.......
########........
#.#.#.#.........
##..##..........
#...#...........
####............
#.#.............
##..............
#...............
*/