传送门
题解： 答案就是行列式的值。 可用可并堆来模拟高斯消元，对于每个主元，每次选择右端点最小去消元，然后把堆中元素全部放到 r+1 r + 1 的地方即可，时间复杂度 O(nlogn). O ( n log n ) . 这道题也提供了一种解 n n 元方程组,且每个方程只出现两个变量的一般方法，只不过需要在堆上加一个tagtag，可以采用从上到下的数据结构（左偏树 /Splay 启发式合并）来完成，时间复杂度 O(nlogn) O ( n log n )
#include <bits/stdc++.h> using namespace std; inline int rd() { char ch=getchar(); int i=0,f=1; while(!isdigit(ch)) {if(ch=='-')f=-1; ch=getchar();} while(isdigit(ch)) {i=(i<<1)+(i<<3)+ch-'0'; ch=getchar();} return i*f; } const int N=1e6+50; int n; struct node { node *lc,*rc; int val,dis,id; }Pool[N],*pool=Pool,*null=Pool,*rt[N],*idx[N]; inline node* newnode(int v,int o) { ++pool; pool->id=o; pool->lc=null; pool->rc=null; pool->val=v; return pool; } inline node* merge(node *x,node *y) { if(x==null) return y; if(y==null) return x; if(x->val>y->val) swap(x,y); x->rc=merge(x->rc,y); if(x->rc->dis>x->lc->dis) swap(x->lc,x->rc); x->dis=x->rc->dis+1; return x; } inline void solve() { pool=Pool; n=rd(); int ans=1; for(int i=1;i<=n;i++) rt[i]=null; for(int i=1;i<=n;i++) { int l=rd(),r=rd(); rt[l]=merge(rt[l],idx[i]=newnode(r,i)); } for(int i=1;i<=n;i++) { if(rt[i]==null || rt[i]->val<i) {puts("Draw"); return;} if(rt[i]!=idx[i]) { idx[i]->id=rt[i]->id; swap(idx[i],idx[rt[i]->id]); rt[i]->id=i; ans=-ans; } int v=rt[i]->val+1; if(v<=n) { rt[i]=merge(rt[i]->lc,rt[i]->rc); rt[v]=merge(rt[v],rt[i]); } } printf("%s\n",(ans<0)?("Fedor"):("Alex")); } int main() { null->dis=-1; for(int i=rd();i;i--) solve(); }