题目大意
一个从0开始的网格图，只有x&y=0的格子(x,y)存在，显然构成以一棵树
设根为(0,0)，初始有一些黑色格子（给出的若干条路径并），A先手，之后AB轮流操作，每次可以把一个黑色格子变白，同时把所有祖先任意变色（各自独立），不能操作者输
现在B想要作弊，每次可以在开始前选一个点把其到根的路径反色，求B获胜的最小操作次数
n<=1e5,x,y<=1e9
题解
ll：简单题
首先考虑判定，可以发现先把所有格子按x+y分类后，只和每个的奇偶性有关
因为如果A操作了某个格子同时改变了祖先奇偶性，则B也可以操作将其还原
所以等价于一行格子，答案显然就是段数
也可以直接考虑sg，因为sg是异或所以反色等于加1，那么一个点(x,y)的sg就是2^(x+y)，因为可以到达0~2^(x+y)-1
于是变成了求路径并，建虚树即可
注意实现，求lca可以每次将平面四分，根据两个点的位置来算，排序就求相对dfs序，先父亲后儿子，如果没有祖先关系就用求lca的方法来分治判断
时间O(nlog^2)
code
#include <bits/stdc++.h>
#define fo(a,b,c) for (a=b; a<=c; a++)
#define fd(a,b,c) for (a=b; a>=c; a--)
#define p(a,b) pair<int,int>(a,b)
#define max(a,b) (a>b?a:b)
#define min(a,b) (a<b?a:b)
#define ll long long
//#define file
using namespace std;
struct type{int x,y,fx,fy;} b[100001][2],c[200001],d[400001],A[400001],D[400001],Lca;
int p[30],a[400001][3],ls[400001],fa[400001],f[400001],g[400001],dp[400001];
int T,n,N,i,j,k,l,t,len,tot,mn,rt,ans;
map<pair<int,int>,int> mp;
map<int,int> mp2;
void look()
{
fo(i,0,50)
{
fo(j,0,50)
cout<<((i&j)==0);
cout<<endl;
}
}
void swap(type &a,type &b) {type c=a;a=b;b=c;}
void New(int x,int y) {++len;a[len][0]=y;a[len][1]=ls[x];ls[x]=len;}
type lca(type a,type b)
{
int i,j,x=0,y=0,X1,Y1,X2,Y2,s1,s2;
fd(i,29,0)
{
X1=(a.x&p[i])>0,Y1=(a.y&p[i])>0;
X2=(b.x&p[i])>0,Y2=(b.y&p[i])>0;
if (X1) s1=1; else if (!Y1) s1=2; else s1=3;
if (X2) s2=1; else if (!Y2) s2=2; else s2=3;
if (s1>s2) j=s1,s1=s2,s2=j,swap(a,b);
if (s1==1 && s2==1) x+=p[i],a.x-=p[i],b.x-=p[i]; else
if (s1==3 && s2==3) y+=p[i],a.y-=p[i],b.y-=p[i]; else
{
if (s1==1) a.x=p[i]-1,a.y=0;
if (s2==3) b.y=p[i]-1,b.x=0;
}
}
return type{x,y};
}
bool cmp(type a,type b)
{
type Lca=lca(a,b);
int i,X1,Y1,X2,Y2,s1,s2;
if (a.x==b.x && a.y==b.y) return 0;
if (Lca.x==a.x && Lca.y==a.y) return 1;
if (Lca.x==b.x && Lca.y==b.y) return 0;
fd(i,29,0)
{
X1=(a.x&p[i])>0,Y1=(a.y&p[i])>0;
X2=(b.x&p[i])>0,Y2=(b.y&p[i])>0;
if (X1) s1=1; else if (!Y1) s1=2; else s1=3;
if (X2) s2=1; else if (!Y2) s2=2; else s2=3;
if (s1!=s2) return s1<s2;
if (s1==1 && s2==1) a.x-=p[i],b.x-=p[i];
if (s1==3 && s2==3) a.y-=p[i],b.y-=p[i];
}
return 0;
}
void build()
{
type Lca,s;
sort(c+1,c+N+1,cmp);
t=1,d[1]=c[1];
fo(i,2,N)
{
Lca=lca(d[t],c[i]),l=0;
while (t && Lca.x+Lca.y<d[t].x+d[t].y)
D[++l]=d[t--];
if (l)
{
fo(j,1,l-1) D[j].fx=D[j+1].x,D[j].fy=D[j+1].y;
D[l].fx=Lca.x,D[l].fy=Lca.y;
while (l) A[++tot]=D[l--];
}
if (!t || Lca.x+Lca.y>d[t].x+d[t].y) d[++t]=Lca;
if (Lca.x+Lca.y<c[i].x+c[i].y) d[++t]=c[i];
}
if (t)
{
fd(j,t,1) d[j].fx=d[j-1].x,d[j].fy=d[j-1].y;
while (t) A[++tot]=d[t--];
}
mn=2000000000;
fo(i,1,tot) mp[p(A[i].x,A[i].y)]=i,mn=min(mn,A[i].x+A[i].y);
fo(i,1,tot)
if (A[i].x+A[i].y>mn)
{
j=mp[p(A[i].x,A[i].y)];
k=mp[p(A[i].fx,A[i].fy)];
New(k,j);
}
else rt=i;
}
void change(int x,int y)
{
int s,s2;--x;
if (x>=0)
s=mp2[x],s2=s^1,ans+=s2-s,mp2[x]=s2;
s=mp2[y],s2=s^1,ans+=s2-s,mp2[y]=s2;
}
void Dfs(int Fa,int t)
{
int i;
dp[t]=A[t].x+A[t].y,fa[t]=Fa;
for (i=ls[t]; i; i=a[i][1]) if (a[i][0]!=Fa) Dfs(t,a[i][0]);
}
void dfs(int Fa,int t)
{
int i;
for (i=ls[t]; i; i=a[i][1])
if (a[i][0]!=Fa)
{
dfs(t,a[i][0]),f[t]+=f[a[i][0]],g[t]+=g[a[i][0]];
if (g[a[i][0]] && dp[t]+1<dp[a[i][0]])
change(dp[t]+1,dp[a[i][0]]-1);
}
if (f[t]) change(dp[t],dp[t]);
}
int main()
{
#ifdef file
freopen("CF1439E.in","r",stdin);
#endif
p[0]=1;
fo(i,1,29) p[i]=p[i-1]*2;
scanf("%d",&n),N=n*2;
fo(i,1,n) scanf("%d%d%d%d",&b[i][0].x,&b[i][0].y,&b[i][1].x,&b[i][1].y),c[i*2-1]=b[i][0],c[i*2]=b[i][1];
build();
Dfs(0,rt);
fo(i,1,n)
{
if (b[i][0].x+b[i][0].y>b[i][1].x+b[i][1].y) swap(b[i][0],b[i][1]);
Lca=lca(b[i][0],b[i][1]);
if (b[i][0].x==b[i][1].x && b[i][0].y==b[i][1].y)
{
j=mp[p(b[i][0].x,b[i][0].y)];
++f[j],--f[fa[j]];
}
else
if (b[i][0].x==Lca.x && b[i][0].y==Lca.y)
{
j=mp[p(b[i][0].x,b[i][0].y)];
k=mp[p(b[i][1].x,b[i][1].y)];
++f[k],--f[fa[j]];
++g[k],--g[j];
}
else
{
j=mp[p(b[i][0].x,b[i][0].y)];
k=mp[p(b[i][1].x,b[i][1].y)];
l=mp[p(Lca.x,Lca.y)];
++f[j],++f[k],--f[l],--f[fa[l]];
++g[j],++g[k],g[l]-=2;
}
}
dfs(0,rt);
printf("%d\n",ans);
fclose(stdin);
fclose(stdout);
return 0;
}