Original link: https://www.shuizilong.com/house/archives/codeforces-tinkoff-challenge-elimination-round/
G. Oleg and chess
Consider network flow first. . . is the simplest bipartite graph matching. . .
Still trying to reduce the size of the edges. . . We use an analogy to scan lines to do rectangle merging. .
Scanning each column from left to right, we can use the functional line segment tree to maintain the root node state of the line segment tree that represents this column. . . Make sure that all segment trees share the same set of closed state nodes.
Then just connect an edge with a capacity of 1 from the source point to the root node. . .
It always feels like there is a better way. . .
This article is reprinted from: https://www.shuizilong.com/house/archives/codeforces-tinkoff-challenge-elimination-round/
This site is for inclusion only, and the copyright belongs to the original author.