??Link.
??给一个 \(n\times n\) 的棋盘，其中 \(q\) 个互不重叠的子矩阵被禁止放棋。问最多能放多少个互不能攻击的车。
??\(n,q\le10^4\)。
??如果把问题转化成“只允许在某些子矩阵上放棋”，就是一个很显然的线段树优化建图最大流。源点连向行上的线段树叶子，流量为 \(1\)；行上的线段树结点向父亲连边，流量为正无穷；对于每个矩阵，行在树上分裂的 $\log $ 个区间分别向列在树上分裂的 \(\log\) 个区间连边，流量为区间长度之积；列上的线段树与行上的类似。
??于是思考怎样转变成这个问题就行了。提供一种方法：延长所有禁用矩阵的横向边，自然地把棋盘切割成若干矩形。用一条扫描线从左往右扫，维护数组 \(lef_i\) 表示第 \(i\) 行目前最右边的障碍。遇到矩阵的左边界就拿来划分，遇到右边界就更新 \(lef\)，\(\mathcal O(n^2)\) 即可实现。（也可以尝试扔一个 Chtholly Tree 上去 www。）
??关于边的复杂度，一个可用矩阵所建出的边是 \(\mathcal O(\log^2n)\) 的，每个可用矩阵必然对应上下两条禁用矩阵边界的延长线，而一个禁用矩阵提供的延长线是 \(\mathcal O(1)\) 的，所以共 \(\mathcal O(q)\) 个矩形，边数总量 \(\mathcal O(n+q\log^2n)\)。
??复杂度 \(\mathcal O(\text{网络瘤})\)（大雾。
#include <queue>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
typedef std::vector<std::pair<int, int> > vecpii;
const int MAXN = 1e4, INF = 0x3f3f3f3f;
int n, q;
inline int rint () {
int x = 0; char s = getchar ();
for ( ; s < ‘0‘ || ‘9‘ < s; s = getchar () );
for ( ; ‘0‘ <= s && s <= ‘9‘; s = getchar () ) x = x * 10 + ( s ^ ‘0‘ );
return x;
}
namespace Dinic {
const int MAXND = MAXN * 5, MAXED = 5e6; // 5e6 ?
int ecnt = 1, S, T, head[MAXND + 5], curh[MAXND + 5], d[MAXND + 5];
struct Edge { int to, flow, nxt; } graph[MAXED * 2 + 5];
inline void link ( const int s, const int t, const int f ) {
graph[++ ecnt] = { t, f, head[s] };
head[s] = ecnt;
}
inline void add ( const int s, const int t, const int f ) {
#ifdef LOCAL_DEBUG
printf ( "%d %d %d\n", s, t, f );
#endif
link ( s, t, f ), link ( t, s, 0 );
}
inline int DFS ( const int u, int iflow ) {
if ( u == T ) return iflow;
int oflow = 0;
for ( int& i = curh[u], v, of; i; i = graph[i].nxt ) {
if ( d[v = graph[i].to] == d[u] + 1 && graph[i].flow ) {
of = DFS ( v, std::min ( iflow, graph[i].flow ) );
oflow += of, graph[i].flow -= of, graph[i ^ 1].flow += of;
if ( ! ( iflow -= of ) ) break;
}
}
if ( ! oflow ) d[u] = -1;
return oflow;
}
inline bool BFS () {
static std::queue<int> que;
for ( int i = 1; i <= T; ++ i ) d[i] = -1;
que.push ( S ), d[S] = 0;
for ( int u; ! que.empty (); que.pop () ) {
u = que.front ();
for ( int i = head[u], v; i; i = graph[i].nxt ) {
if ( ! ~ d[v = graph[i].to] && graph[i].flow ) {
que.push ( v ), d[v] = d[u] + 1;
}
}
}
return ~ d[T];
}
inline int calc () {
int ret = 0;
for ( ; BFS (); ret += DFS ( S, INF ) ) {
for ( int i = 1; i <= T; ++ i ) {
curh[i] = head[i];
}
}
return ret;
}
} // namespace Dinic.
namespace SegmentTree {
int sizt;
inline int id ( const int l, const int r, const bool type ) {
return type * sizt + ( ( l + r ) | ( l != r ) );
}
inline void build ( const int l, const int r, const bool type ) {
int rt = id ( l, r, type ), mid = l + r >> 1;
if ( l == r ) {
if ( ! type ) Dinic::add ( Dinic::S, rt, 1 );
else Dinic::add ( rt, Dinic::T, 1 );
return ;
}
if ( ! type ) {
Dinic::add ( id ( l, mid, type ), rt, INF );
Dinic::add ( id ( mid + 1, r, type ), rt, INF );
} else {
Dinic::add ( rt, id ( l, mid, type ), INF );
Dinic::add ( rt, id ( mid + 1, r, type ), INF );
}
build ( l, mid, type ), build ( mid + 1, r, type );
}
inline void extract ( const int l, const int r, const int el, const int er, const bool type, vecpii& vec ) {
int rt = id ( l, r, type ), mid = l + r >> 1;
if ( el <= l && r <= er ) return vec.push_back ( { rt, r - l + 1 } );
if ( el <= mid ) extract ( l, mid, el, er, type, vec );
if ( mid < er ) extract ( mid + 1, r, el, er, type, vec );
}
inline void init () {
sizt = id ( n, n, 0 );
Dinic::S = sizt * 2 + 3, Dinic::T = Dinic::S + 1;
build ( 1, n, 0 ), build ( 1, n, 1 );
}
inline void secLink ( const int rl, const int rr, const int cl, const int cr ) {
#ifdef LOCAL_DEBUG
printf ( "sl %d %d %d %d\n", rl, rr, cl, cr );
#endif
static vecpii R, C; R.clear (), C.clear ();
extract ( 1, n, rl, rr, 0, R ), extract ( 1, n, cl, cr, 1, C );
for ( auto r: R ) for ( auto c: C ) Dinic::add ( r.first, c.first, r.second * c.second );
}
} // namespace SegmentTree.
namespace Partition {
int scnt, lef[MAXN + 5];
struct Segment {
int r1, r2, c; bool type;
inline bool operator < ( const Segment t ) const {
return c ^ t.c ? c < t.c : type < t.type;
}
} seg[MAXN * 2 + 5];
inline void readSeg () {
for ( int i = 1, r1, c1, r2, c2; i <= q; ++ i ) {
r1 = rint (), c1 = rint (), r2 = rint (), c2 = rint ();
seg[++ scnt] = { r1, r2, c1, 0 }, seg[++ scnt] = { r1, r2, c2, 1 };
}
seg[++ scnt] = { 1, n, n + 1, 0 }, seg[++ scnt] = { 1, n, n + 1, 1 };
}
inline void part () {
std::sort ( seg + 1, seg + scnt + 1 );
for ( int i = 1; i <= scnt; ++ i ) {
if ( seg[i].type ) {
for ( int j = seg[i].r1; j <= seg[i].r2; ++ j ) {
lef[j] = seg[i].c;
}
} else {
for ( int j = seg[i].r1, lasw = seg[i].c - 1, lash = 0; j <= seg[i].r2 + 1; ++ j ) {
if ( j == seg[i].r2 + 1 || lef[j] ^ lasw ) {
if ( lasw + 1 < seg[i].c ) {
SegmentTree::secLink ( lash, j - 1, lasw + 1, seg[i].c - 1 );
}
lasw = lef[j], lash = j;
}
}
}
}
}
} // namespace Partition.
int main () {
n = rint (), q = rint ();
Partition::readSeg ();
SegmentTree::init ();
Partition::part ();
printf ( "%d\n", Dinic::calc () );
return 0;
}
Solution -「CF 793G」Oleg and Chess
原文：https://www.cnblogs.com/rainybunny/p/13455069.html