题解：CF2041G Grid Game
题目要求割点数量。
若
先添加两条黑线
做过某贺 tj 重灾区的（我没做过）应该都知道，距离黑线和边界
也就是，我们把线按照
现在需要对每一列进行“缩点”。对于同一列上的连续两个点，如果其周围的
具体的，我们把连续三列拉出来，则中间列某一行的点能成为“
基于这个原则，我们已经将点数缩为
::::info[这种情况的建图]
此时点分为两类。一种是白连续段的端点（单点），一种是原来若干个连续点缩成的长点。我们只需要求出这个图的割点的权值（大小）和即可。
以下是题面中的图建出来的东西。
:::warning[以上的图多了一条边]
多了
由于我没原图了，编辑不了。懒得重画了。
:::
::::
刚才那个当然是可以写的。只不过我们发现长点之间连边比较麻烦（需要双指针之类的东西）。
事实上我们可以发现，长点之间的连边是不必要的！
如上图左，中间的红边是两个长点之间的连边，我们将其删除之后不影响双连通性。类似地可以发现，横向的长单点之间的边也可以删去。
可以发现，此时长点的唯一作用就是连接其上下两个点了。所以，可以将长点变成上下两点间的带权边（如上图右）。
::::info[这种情况的建图]{open}
点数肯定是
这个时候我们需要求出割点的个数
::::
::::success[代码] 提交链接
#include <algorithm>
#include <iostream>
#include <vector>
#include <map>
using namespace std;
#define MAXN 600005
#define MAXM 1000000009
using ll = long long;
ll n;
int q;
struct Line
{
ll x;
ll l, r;
bool operator<(const ll &a) const
{
return r < a;
}
} v[MAXN];
vector<Line> vs[MAXN];
map<ll, int> mp[MAXN];
int nid = 0;
struct Edge
{
int u, v;
ll w;
} e[MAXN << 4];
int h[MAXN];
int idx = 1;
void add(int u, int v, ll w)
{
e[++idx] = {h[u], v, w};
h[u] = idx;
e[++idx] = {h[v], u, w};
h[v] = idx;
}
ll res = 0;
int dfn[MAXN], low[MAXN], dfc = 0;
bool vis[MAXN];
void tarjan1(int p, int fr) // Vertex-BCC
{
dfn[p] = low[p] = ++dfc;
int c = 0;
for (int i = h[p]; i; i = e[i].u)
{
int u = e[i].v;
if (!dfn[u])
{
c++;
tarjan1(u, i);
if (fr && low[u] >= dfn[p] && !vis[p])
{
res++;
vis[p] = true;
}
low[p] = min(low[p], low[u]);
}
else if (fr && i != (fr ^ 1))
{
low[p] = min(low[p], dfn[u]);
}
}
if (c > 1 && !fr && !vis[p])
{
res++;
vis[p] = true;
}
}
void tarjan2(int p, int fr) // Edge-BCC
{
dfn[p] = low[p] = ++dfc;
for (int i = h[p]; i; i = e[i].u)
{
int u = e[i].v;
if (!dfn[u])
{
tarjan2(u, i);
low[p] = min(low[p], low[u]);
if (low[u] > dfn[p])
{
res += e[i].w;
}
}
else if (i != (fr ^ 1))
{
low[p] = min(low[p], dfn[u]);
}
}
}
void solve()
{
cin >> n >> q;
for (int i = 1; i <= q; i++)
{
cin >> v[i].x >> v[i].l >> v[i].r;
}
v[++q] = {n + 1, 1, n};
v[++q] = {0, 1, n};
sort(v + 1, v + q + 1, [] (const Line &a, const Line &b) {
if (a.x == b.x)
{
return a.l < b.l;
}
return a.x < b.x;
});
for (int i = q; i; i--)
{
v[i].x = min(3ll, v[i].x - v[i - 1].x);
}
for (int i = 1; i <= q; i++)
{
v[i].x += v[i - 1].x;
vs[v[i].x].push_back(v[i]);
}
for (int i = 1; i < v[q].x; i++)
{
vector<Line> cur;
for (Line l : vs[i])
{
if (!cur.empty() && cur.back().r + 2 > l.l)
{
cur.back().r = max(cur.back().r, l.r);
}
else
{
cur.push_back(l);
}
}
vs[i].swap(cur);
}
for (int i = 1; i < v[q].x; i++)
{
vector<ll> cur{1, n};
for (Line l : vs[i])
{
cur.push_back(l.l - 1);
cur.push_back(l.r + 1);
}
for (Line l : vs[i - 1])
{
cur.push_back(l.l - 1);
cur.push_back(l.r + 1);
}
for (Line l : vs[i + 1])
{
cur.push_back(l.l - 1);
cur.push_back(l.r + 1);
}
sort(cur.begin(), cur.end());
cur.erase(unique(cur.begin(), cur.end()), cur.end());
vector<ll> tmp;
for (ll p : cur)
{
if (p < 1 || p > n)
{
continue;
}
auto it = lower_bound(vs[i].begin(), vs[i].end(), p);
if (it == vs[i].end() || it->l > p)
{
tmp.push_back(p);
}
}
tmp.swap(cur);
for (ll p : cur)
{
mp[i][p] = ++nid;
if (mp[i - 1].count(p))
{
add(mp[i][p], mp[i - 1][p], 0);
}
}
for (int j = 0; j < (int)cur.size() - 1; j++)
{
ll a = cur[j], b = cur[j + 1];
auto ita = lower_bound(vs[i].begin(), vs[i].end(), a), itb = lower_bound(vs[i].begin(), vs[i].end(), b);
if (ita == itb)
{
add(mp[i][a], mp[i][b], b - a - 1);
}
}
}
tarjan1(1, 0);
fill(dfn + 1, dfn + nid + 1, 0);
fill(low + 1, low + nid + 1, 0);
dfc = 0;
tarjan2(1, 0);
cout << res << '\n';
// Clear
for (int i = 0; i <= v[q].x; i++)
{
vs[i].clear();
mp[i].clear();
}
fill(dfn + 1, dfn + nid + 1, 0);
fill(low + 1, low + nid + 1, 0);
fill(vis + 1, vis + nid + 1, false);
fill(h + 1, h + nid + 1, 0);
nid = 0;
res = 0;
idx = 1;
dfc = 0;
}
int main()
{
int t;
cin >> t;
while (t--)
{
solve();
}
return 0;
}
:::error[警钟敲烂]{open}
在同一列内连边的时候，你可能需要遍历 vector 的前 vector::size() - 1，那就寄了。
size_t 为无符号整数，
::::