## 【BZOJ 1997】[Hnoi2010] Planar

1.圆内
2.圆外

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.

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

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

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;

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(){
for (int i=1;i<=n;i++) G[i].clear();
memset(mark,0,sizeof(mark));
}

inline void AddEdge(int a, int b) {
int ra=a*2+1, rb=b*2+1; a *= 2; b *= 2;
}

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++)
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;

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<=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;
}