【CodeChef-BWGAME】Black-white Board Game（可并堆）（高斯消元）

传送门

---

题解：

首先读题，很显然答案就是行列式的值。

由于矩阵是每行有一段连续的一，显然消元之后每行也是一段连续的一。

我们直接用可并堆枚举左端点，维护一下右端点的位置，然后消元的时候相当于直接取右端点最靠前的，然后把剩下的并过去即可。

模拟即可

---

代码：

#include<bits/stdc++.h>
#define ll long long
#define re register
#define gc get_char
#define cs const

namespace IO{
	inline char get_char(){
		static cs int Rlen=1<<22|1;
		static char buf[Rlen],*p1,*p2;
		return (p1==p2)&&(p2=(p1=buf)+fread(buf,1,Rlen,stdin),p1==p2)?EOF:*p1++; 
	}
	template<typename T>
	inline T get(){
		char c;T num;
		while(!isdigit(c=gc()));num=c^48;
		while(isdigit(c=gc()))num=(num+(num<<2)<<1)+(c^48);
		return num;
	}
	inline int gi(){return get<int>();}
}
using namespace IO;

using std::cerr;
using std::cout;

cs int N=1e6+7;

int n,now;

int lc[N],rc[N],ht[N]; 
int val[N],id[N];

int rt[N],idx[N];
inline int newnode(int v,int i){
	int u=++now;
	val[u]=v,id[u]=i;
	lc[u]=rc[u]=ht[u]=0;
	return u;
}
inline int merge(int u,int v){
	if(!u||!v)return u|v;
	if(val[u]>val[v])std::swap(u,v);
	rc[u]=merge(rc[u],v);
	if(ht[rc[u]]>ht[lc[u]])std::swap(lc[u],rc[u]);
	ht[u]=ht[rc[u]]+1;
	return u;
}

inline void solve(){
	now=0;n=gi();int ans=1;
	for(int re i=1;i<=n;++i)rt[i]=0;
	for(int re i=1;i<=n;++i){
		int l=gi(),r=gi();
		rt[l]=merge(rt[l],idx[i]=newnode(r,i));
	}
	for(int re i=1;i<=n;++i){
		if(!rt[i]||val[rt[i]]<i){puts("Draw");return ;}
		if(rt[i]!=idx[i]){
			id[idx[i]]=id[rt[i]];
			std::swap(idx[i],idx[id[rt[i]]]);
			id[rt[i]]=i,ans=-ans;
		}
		int v=val[rt[i]]+1;
		if(v<=n)rt[v]=merge(rt[v],merge(lc[rt[i]],rc[rt[i]]));
	}
	puts(ans<0?"Fedor":"Alex");
}

signed main(){
#ifdef zxyoi
	freopen("BWGAME.in","r",stdin);
#endif
	ht[0]=-1;
	int T=gi();
	while(T--)solve();
	return 0;
}