BZOJ 3714 Kuglarz

BZOJ 3714 Kuglarz

非常玄学的一道题....到现在还没理解为什么是最小生成树的题...
这里就从另一个角度解析题目，首先题目中每个杯子中是否藏有球可以视为0/1，而我们询问的一个区间的奇偶可以看做是若干个变量相异或的和，而每个变量的意义就是该杯子下是否藏有求0/1.那么我们的目的是想知道这n个变量的值，根据线性代数的一些知识，我们知道解出n个变量的唯一解的冲要条件是有n个本质上不同的方程(其实这也可以通过手玩样例来得出)。那我们怎么来选出这n个方程，并且维护他们是否已经被已有的方程给生成了。我们可以举个例子就能简单的判断，第一个方程：l-mid，第二个方程mid+1，r，第三个方程，l，r。显然第三个方程可以被前两个方程相加得到。维护关系的话我们很容易想到的就在边界处两边，可直接在l-mid，和mid+1-r连边，无法看出l和r的关系。同时我们发现只有相邻的时候才会合并，那我们将l-mid+1连边，mid+1-r连边即可。这样的话l-r就联通，说明l-r这个区间就不行了。那我们知道最后n个方程，即n个边最后的结果就是1到n+1的一个最小生成树。

#include
#define ll long long
using namespace std;
const int N=2010;
int n,f[N],num;
struct wy{int x,y,v;}a[N*N*2]; 
inline int getf(int x){return f[x]==x?x:f[x]=getf(f[x]);}
inline bool cmp(wy a,wy b){return a.v