[图论] 平面图做题笔记
平面图，即能在二维平面中画出来的图，满足边不相交。
对偶图，即把每个面看作点，每条边看作连接两个面的边建出的图。
应用一：最小割
给一张平面图，要求断一些边使得起点和终点不连通，问最小代价。
解法：把对偶图建出来，跑最短路即可。
模板题：P4001 P2046
进阶题：P4646
思维题：P7916，这道题初看是多源多汇，最短路好像不太能做？但是手推几组数据，我们发现既然合法方案在对偶图中的路径都不交，就如同括号匹配那样，不会出现交叉匹配的情况，那么套一个区间 dp 就可以了。
应用二：平面定位、点定位
首先，如果给你的图不是方方正正的，怎么建对偶图呢？
对于每个点，记录与它相连的边，存在 vector 里面，并按照 tan 值（极角序）排序。我们考虑遍历每条边：当走过一条从
由于这个算法的结果是把每个封闭图形都顺时针画了一遍，它有个名字叫最小左转法。
注意：利用这个顺时针的性质结合计算几何可知，如果一个封闭图形按照向量叉积得到的面积是正的，那么它就是封闭图形的边缘，外面是无限大的面（或者完全包含它的一个面）。
以上这个性质很重要，后面有着不少应用。
然后，如何确定一个点属于哪个平面？
这个也不难，扫描线扫一扫，平衡树维护若干条一次函数（或者说向量），遇到一个点就看看它夹在哪两条一次函数之间。如果没有夹在两条一次函数之间，说明它在整个平面图外面。
模板题：P4073，就是刚才的内容套上 kruskal 重构树，300 行之内就能写完。
进阶题：P3249，套完模板后转化成了树上求和问题，简单子树加和即可。
应用三：平面图欧拉定理
分别代表点数、边数、面数。
注意：公式适用于平面图联通的情况。若不联通，则需要加上（减去）完全包含所产生的镂空面（例子：大正方形套小正方形，你会发现这个公式里凭空多出一个面，原因是连通块数量为二）
进阶题：P3776，使用这个公式计算即可。原题强制在线（尽管洛谷不用），那么主席树就能解决。注意特判刚才说到的不连通情况。
综合应用
例题一：
P7295，对欧拉公式的处理用二维前缀和就行了，重点是如何统计连通块数量。
考虑到应用二中所说到的注意事项，我们可以把极大图形都求出来，并记录它们的最小纵横坐标，最大纵横坐标。只有一个矩形完全包含这几个坐标，才会产生新连通块，那么可以上最小左转法 + cdq 分治（四维偏序）。
例题二：
P8192，由于点数过多，还要分别算黑白数量，欧拉公式不能直接应用。但是
但是我们发现，对于应用三中的注意事项我们无能为力，因为不能确定一条竖线的上下方是否同属一个区域，也就是分不清矩形完全包含和矩形相交（小矩形插入大矩形），进而不知道答案应该减一还是不变。
“是否同属一个区域”启示我们用并查集，那么解法就有了：
#include <bits/stdc++.h>
#define lowbit(x) (x & (-x))
using namespace std;
const int N = 200010;
int n, T; long long B, W = 1;
struct Line {int opt, x, sy, ty;}; Line li[N]; int ln;
inline bool cmpx(Line u, Line v) {return u.x < v.x;}
int sign;
struct DSU
{
int prt[N * 4], siz[N * 4];
inline int newnode()
{
++sign; prt[sign] = sign;
siz[sign] = 1; return sign;
}
inline int find(int x)
{
if(prt[x] == x) return x;
prt[x] = find(prt[x]);
return prt[x];
}
inline void merge(int x, int y)
{
int u = find(x), v = find(y);
if(u != v)
{
if(siz[u] > siz[v]) swap(u, v);
prt[u] = v, siz[v] += siz[u], siz[u] = 0;
}
}
}; DSU dsu;
set < int > st;
int rt, idx;
struct SGT
{
int ls, rs, lm, rm, sum, tag;
int col, tc;
#define ls(x) tree[x].ls
#define rs(x) tree[x].rs
#define lm(x) tree[x].lm
#define rm(x) tree[x].rm
#define sum(x) tree[x].sum
#define tag(x) tree[x].tag
#define col(x) tree[x].col
#define tc(x) tree[x].tc
}tree[N * 2];
inline void pushup(int now)
{
lm(now) = lm(ls(now)); rm(now) = rm(rs(now));
sum(now) = sum(ls(now)) + sum(rs(now)) + (rm(ls(now)) != lm(rs(now)));
}
inline void push_cov(int now, int tg) {col(now) = tc(now) = tg;}
inline void push_rev(int now)
{
lm(now) = 1 - lm(now); rm(now) = 1 - rm(now);
tag(now) ^= 1;
}
inline void pushdown(int now)
{
if(tag(now))
{
push_rev(ls(now));
push_rev(rs(now));
tag(now) = 0;
}
if(tc(now))
{
push_cov(ls(now), tc(now));
push_cov(rs(now), tc(now));
tc(now) = 0;
}
}
inline void build(int &now, int l, int r)
{
now = ++idx; col(now) = 1;
if(l == r) return ;
int mid = (l + r) >> 1;
build(ls(now), l, mid); build(rs(now), mid + 1, r);
pushup(now);
}
inline void insert(int now, int l, int r, int L, int R)
{
if(L <= l && r <= R) {push_rev(now); return ;}
pushdown(now); int mid = (l + r) >> 1;
if(L <= mid) insert(ls(now), l, mid, L, R);
if(mid < R) insert(rs(now), mid + 1, r, L, R);
pushup(now);
}
inline int check(int now, int l, int r, int pos)
{
if(l == r) return lm(now);
pushdown(now); int mid = (l + r) >> 1;
if(pos <= mid) return check(ls(now), l, mid, pos);
return check(rs(now), mid + 1, r, pos);
}
inline int query(int now, int l, int r, int L, int R)
{
if(L <= l && r <= R) return sum(now);
pushdown(now); int mid = (l + r) >> 1;
if(R <= mid) return query(ls(now), l, mid, L, R);
else if(mid < L) return query(rs(now), mid + 1, r, L, R);
else return query(ls(now), l, mid, L, R) + query(rs(now), mid + 1, r, L, R) + (rm(ls(now)) != lm(rs(now)));
}
inline void output(int now, int l, int r)
{
if(l == r) {if(col(now) == -1) cout << -1 << " "; else cerr << dsu.find(col(now)) << " "; return ;}
pushdown(now); int mid = (l + r) >> 1;
output(ls(now), l, mid);
output(rs(now), mid + 1, r);
}
inline void color(int now, int l, int r, int L, int R, int num)
{
// if(l == 1 && r == 2 * n) cout << "Col " << L << " " << R << " " << num << '\n';
if(L <= l && r <= R) {push_cov(now, num); return ;}
pushdown(now); int mid = (l + r) >> 1;
if(L <= mid) color(ls(now), l, mid, L, R, num);
if(mid < R) color(rs(now), mid + 1, r, L, R, num);
pushup(now);
}
inline int getcol(int now, int l, int r, int pos)
{
if(pos == 0) return 1;
if(l == r) return col(now);
pushdown(now); int mid = (l + r) >> 1;
if(pos <= mid) return getcol(ls(now), l, mid, pos);
return getcol(rs(now), mid + 1, r, pos);
}
inline int findL(int now, int l, int r, int lim)
{
if(sum(now) == 0) return r;
pushdown(now); int mid = (l + r) >> 1;
if(lim > mid) return findL(rs(now), mid + 1, r, lim);
else
{
int res = findL(ls(now), l, mid, lim);
if(res == mid && rm(ls(now)) == lm(rs(now)))
return findL(rs(now), mid + 1, r, lim);
return res;
}
}
inline int findR(int now, int l, int r, int lim)
{
if(sum(now) == 0) return l;
pushdown(now); int mid = (l + r) >> 1;
if(lim <= mid) return findR(ls(now), l, mid, lim);
else
{
int res = findR(rs(now), mid + 1, r, lim);
if(res == mid + 1 && rm(ls(now)) == lm(rs(now)))
return findR(ls(now), l, mid, lim);
return res;
}
}
int main()
{
// freopen("text.in", "r", stdin);
// freopen("prog.out", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
dsu.newnode();
cin >> n >> T;
for(int i = 1; i <= n; ++i)
{
int sx, sy, tx, ty; cin >> sx >> sy >> tx >> ty;
li[++ln].opt = 1, li[ln].x = sx, li[ln].sy = sy, li[ln].ty = ty;
li[++ln].opt = 2, li[ln].x = tx, li[ln].sy = sy, li[ln].ty = ty;
}
sort(li + 1, li + ln + 1, cmpx);
build(rt, 1, 2 * n);
for(int i = 1; i <= ln; ++i)
{
int l = li[i].sy, r = li[i].ty - 1;
// cerr << "-----------------------------------\n";
// cerr << "line " << li[i].opt << " " << l << " " << r << "\n";
if(li[i].opt == 1)
{
insert(rt, 1, 2 * n, l, r);
int bs = check(rt, 1, 2 * n, l);
int dv = query(rt, 1, 2 * n, l, r);
if(bs == 0) W += 1 + dv / 2, B += (dv + 1) / 2;
else B += 1 + dv / 2, W += (dv + 1) / 2;
color(rt, 1, 2 * n, l, r, -1);
int exl = findR(rt, 1, 2 * n, r);
int exr = findL(rt, 1, 2 * n, l);
color(rt, 1, 2 * n, l, exr, dsu.newnode());
color(rt, 1, 2 * n, exl, r, dsu.newnode());
}
else
{
insert(rt, 1, 2 * n, l, r);
int bs = check(rt, 1, 2 * n, l);
int dv = query(rt, 1, 2 * n, l, r);
if(dv == 0)
{
int cl = getcol(rt, 1, 2 * n, l - 1);
int cr = getcol(rt, 1, 2 * n, r + 1);
if(cl == -1 && cr == -1)
{
color(rt, 1, 2 * n, l, r, -1);
if(bs == 0) --W;
else --B;
}
else if(min(cl, cr) == -1 && max(cl, cr) != -1)
{
int exl = findR(rt, 1, 2 * n, r);
int exr = findL(rt, 1, 2 * n, l);
color(rt, 1, 2 * n, exl, exr, max(cl, cr));
if(bs == 0) --W;
else --B;
}
else
{
color(rt, 1, 2 * n, l, r, cl);
if(dsu.find(cl) != dsu.find(cr))
{
dsu.merge(cl, cr);
if(bs == 0) --W;
else --B;
}
}
}
else
{
if(bs == 0) B += dv / 2, W += (dv - 1) / 2;
else W += dv / 2, B += (dv - 1) / 2;
int exl = findR(rt, 1, 2 * n, r);
int exr = findL(rt, 1, 2 * n, l);
if(exr + 1 <= exl - 1)
color(rt, 1, 2 * n, exr + 1, exl - 1, -1);
int cl = getcol(rt, 1, 2 * n, l - 1);
int cr = getcol(rt, 1, 2 * n, r + 1);
color(rt, 1, 2 * n, l, exr, cl);
color(rt, 1, 2 * n, exl, r, cr);
}
}
// output(rt, 1, 2 * n); cerr << '\n';
// cerr << "ans " << W << " " << B << '\n';
}
if(T == 1) cout << W + B << '\n';
else cout << W << " " << B << '\n';
return 0;
}
/*
2 2
1 1 3 3
2 2 4 4
*/更详细的可以看看这题的第一篇题解。