【BZOJ 1997】[Hnoi2010] Planar

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=1997
数据生成器:http://paste.ubuntu.com/22273507/

这个题目在知道了是2-sat的情况下还是懵逼了好久QAQ
当时就想到这个图:一个正方形加上对角线.jpg(solidwork还没装,不想用word画图QAQ
发现他给的这个圆不能自交,于是每一条线就只有两种可能:
1.圆内
2.圆外
于是处理出相互干涉的线段,然后搞2-sat

最开始这么搞了,血RE
遂看题解,™有一个这个结论:
Theorem 1. If v ≥ 3 then e ≤ 3v − 6;
Theorem 2. If v ≥ 3 and there are no cycles of length 3, then e ≤ 2v − 4.
详细情况:https://en.wikipedia.org/wiki/Planar_graph
于是加特判,遂过

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<set>
#include<map>
using namespace std;

const int MAXN = 20000+9;
const int N = 200000;

int n,m,que[MAXN],L[MAXN],R[MAXN],T,nxt[N],to[N],head[MAXN],mark[MAXN],cnt;
vector<int> G[MAXN];
map<int,int> ins;

struct CMP{inline bool operator () (const int &A, const int &B) {return R[A] < R[B];}};
multiset<int,CMP>::iterator itr;
multiset<int,CMP> buf;


inline int read(){
	char c=getchar(); int ret=0;
	while (c<'0'||c>'9'){c=getchar();}
	while (c<='9'&&c>='0'){ret=ret*10+c-'0';c=getchar();}
	return ret;
}

inline void init(){
	n = read(); m = read(); T = 0;
	for (int i=1;i<=n;i++) G[i].clear();
	memset(head,0,sizeof(head));
	memset(mark,0,sizeof(mark));
}

#define Add_Edge(a,b) to[++T] = b,nxt[T]=head[a],head[a]=T
inline void AddEdge(int a, int b) {
	int ra=a*2+1, rb=b*2+1; a *= 2; b *= 2;
	Add_Edge(ra,b); Add_Edge(rb,a);
	Add_Edge(a,rb); Add_Edge(b,ra);
}

inline void build_map(){
	buf.clear();
	for (int i=1;i<=n;i++) {
		while (buf.size() && R[*(buf.begin())] <= i) buf.erase(buf.begin());
		for (int j=0,sz=G[i].size();j<sz;j++) 
			for (itr=buf.begin();itr!=buf.end() && R[*itr] < R[G[i][j]];itr++) 
				AddEdge(G[i][j],*itr);
		for (int j=0,sz=G[i].size();j<sz;j++) buf.insert(G[i][j]);
	}
}

bool DFS(int w) {
	if (mark[w]) return true;
	if (mark[w^1]) return false;
	mark[w] = 1; que[++cnt] = w;
	
	for (int i=head[w];i;i=nxt[i]) 
		if (!DFS(to[i])) return false;
	return true;
}

inline bool judge(){
	for (int i=2;i<=m*2+1;i+=2) if (!mark[i] && !mark[i+1]) {
		cnt = 0; if (DFS(i)) continue;
		for (int j=1;j<=cnt;j++) mark[que[j]] = 0;
		cnt = 0; if (!DFS(i+1)) return false; 
	}
	return true;
}

int main(){
	int TT = read(); while (TT--) { init();
		for (int i=1;i<=m;i++) L[i] = read(), R[i] = read();
		for (int i=1;i<=n;i++) que[i] = read(), ins[que[i]] = i;
		for (int i=1;i<=m;i++) {
			L[i] = ins[L[i]]; R[i] = ins[R[i]];
			if (L[i] > R[i]) swap(L[i], R[i]);
			G[L[i]].push_back(i);
		}
		if (m > 3*n-6) printf("NO\n");
		else {
			build_map();
			if (judge()) printf("YES\n");
			else printf("NO\n");
		}
	} 
	return 0;
}