NAC2022
Contents
G. Rafting Trip
题意
给定一个 $n \times m$ 的网格，每个网格要么是河流，要么是陆地。
如果是河流，那么它一定是上下左右四个方向之一，代表走到这个位置，下一个位置就会被冲到对应方向一格的位置。
如果是陆地，要么是空地，要么是一个观光点。
我们可以选定从一个点出发，顺着河流的流向前进，当我们走到陆地/场地外/一个走过的点时，将会结束旅程。
旅程中，如果我们在河流上，并且邻居有观光点，那么我们可以记录这个观光点。
对于所有的出发点，求最优的出发点，使得旅程中记录到的观光点最多（每个观光点不能被重复记录）。
其中，$n,m \leq 500$。
题解
注意到如果是河流，只会有上下左右四个方向。所以每个点只有至多1个出边。这说明什么？基环树！（更准确的说是基环森林）。
虽然这题是有向边，但处理基环树我们直接当无向边做就可以了。
所以我们先建无向图，只考虑河流，陆地就直接忽略。
然后我们先找到基环树中的环，然后缩点，这样就得到一个树了。以环作为根，跑 dfs 即可。
如果没有环，就取一个没有出边的点作为根。
• 这样看起来 dfs 的过程是跑了反向的边，但实际上为了统计这个观光点，必须按照反向的顺序来。
• 缩点后不用重新建图，建一个新点即可，注意新点向被缩的点的邻居们连边，要check一下不能连到环上的点。
基环树找环-注意事项
然后是需要特别注意的基环树找环问题。
注意到这个题目，基环树可能会有大小为 $2$ 的环，这样就会有重边了。
所以我们在第一次dfs找环时，不能直接记录 parent 的 vertex。
而是应该记录 parent 的边，并且用前向星建图。
举个例子，1->2, 2->1。
如果我们用 if (par[v] == u) continue; 的话，到了 2 时就会直接忽略掉 1。然后回到 1 的时候，由于有重边，1会发现 vis[2] = 1;，这样看起来 1 是cycle的终点，2是cycle的起点，实际上是反过来的！
所以正确的写法是：
vector<int> cycle, comp; // component: 储存这个联通分量的所有点
void dfs1(int u, int in_edge) { // 这里的参数是 e的编号！
vis[u] = 1;
comp.push_back(u);
for (int e = head[u]; e; e = edges[e].nxt) {
if (e == (in_edge ^ 1)) continue; // 特意处理了大小为2的环，注意这里 (in_edge^1) 需要加括号！
int v = edges[e].to;
if (vis[v]) {
if (!cycle.size()) { // 只跑一个cycle！因为有重边！
int c = u;
while (c != v) {
cycle.push_back(c);
c = pre[c];
}
cycle.push_back(c);
for (int j : cycle) iscycle[j] = 1;
}
} else {
pre[v] = u;
dfs1(v, e); // 注意这里参数是 e
}
}
}
代码
#include <bits/stdc++.h>
using namespace std;
const int maxn = 500+5;
const int maxm = (500*500+105) * 2;
int n,m;
char grid[maxn][maxn];
int id[maxn][maxn];
bool river[maxn][maxn], site[maxn][maxn];
bool ok(int i, int j) {
return i >= 1 && i <= n && j >= 1 && j <= m && river[i][j];
}
vector<int> adj[maxm];
vector<int> adj_site[maxm];
int d[4][2] = {{1,0}, {-1,0}, {0,1}, {0,-1}};
struct Edge {
int to, nxt;
} edges[maxm<<1];
int head[maxm], ecnt = 2;
void addEdge(int u, int v) {
Edge e = {v, head[u]};
edges[ecnt] = e;
head[u] = ecnt++;
}
bool vis[maxm], iscycle[maxm];
int pre[maxm], outdeg[maxm];
vector<int> cycle, comp; // component: 储存这个联通分量的所有点
void dfs1(int u, int in_edge) {
vis[u] = 1;
comp.push_back(u);
for (int e = head[u]; e; e = edges[e].nxt) {
if (e == (in_edge ^ 1)) continue; // 特意处理了大小为2的环，注意这里 (in_edge^1) 需要加括号！
int v = edges[e].to;
if (vis[v]) {
if (!cycle.size()) {
int c = u;
while (c != v) {
cycle.push_back(c);
c = pre[c];
assert(c != 0);
}
assert(c == v);
cycle.push_back(c);
for (int j : cycle) iscycle[j] = 1;
}
} else {
pre[v] = u;
dfs1(v, e); // 注意这里参数是 e
}
}
}
int cid = 0;
int cnt[maxm], res = 0, ans = 0;
void dfs2(int u, int p) {
for (int v : adj_site[u]) {
if (!cnt[v]) res++;
cnt[v]++;
}
ans = max(ans, res);
for (int v : adj[u]) {
if (v == p || iscycle[v]) continue; // 已经是cycle的说明被缩点缩掉了，删去
dfs2(v, u);
}
// 回溯
for (int v : adj_site[u]) {
cnt[v]--;
if (!cnt[v]) res--;
}
}
void solve(int u) {
cycle.clear();
comp.clear();
dfs1(u, 0);
int rt = -1;
if (cycle.size()) {
// 有环
rt = ++cid;
for (int v : cycle) {
for (int j : adj_site[v]) {
adj_site[rt].push_back(j);
}
for (int nv : adj[v]) {
if (!iscycle[nv]) { // 只考虑不是cycle上的点
adj[rt].push_back(nv);
}
}
}
iscycle[rt] = 1;
sort(adj[rt].begin(), adj[rt].end());
adj[rt].resize(unique(adj[rt].begin(), adj[rt].end()) - adj[rt].begin());
sort(adj_site[rt].begin(), adj_site[rt].end());
adj_site[rt].resize(unique(adj_site[rt].begin(), adj_site[rt].end()) - adj_site[rt].begin());
} else {
for (int v : comp) {
if (!outdeg[v]) {
rt = v;
break;
}
}
assert(rt != -1);
}
dfs2(rt, 0);
}
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
string s; cin >> s;
for (int j = 1; j <= m; j++) {
grid[i][j] = s[j-1], id[i][j] = ++cid;
if (grid[i][j] != '.' && grid[i][j] != '#') river[i][j] = 1;
if (grid[i][j] == '#') site[i][j] = 1;
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
int u = id[i][j];
int op;
if (grid[i][j] == 'v') op = 0;
if (grid[i][j] == '^') op = 1;
if (grid[i][j] == '>') op = 2;
if (grid[i][j] == '<') op = 3;
int ni = i + d[op][0], nj = j + d[op][1];
if (ok(ni, nj)) {
int v = id[ni][nj];
addEdge(u,v);
addEdge(v,u);
adj[u].push_back(v);
adj[v].push_back(u);
outdeg[u]++; // outdeg = 0的就是树的根
}
// adj_site (only consider river's neighbor)
if (river[i][j]) {
for (int o = 0; o < 4; o++) {
int ni = i + d[o][0], nj = j + d[o][1];
if (site[ni][nj]) {
adj_site[u].push_back(id[ni][nj]);
}
}
}
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (river[i][j]) {
int u = id[i][j];
if (!vis[u]) solve(u);
}
}
}
cout << ans << endl;
}
L. Triangular Logs
题意
二维空间中有 $n$ 个点，每个点 $(x_i,y_i)$ 有一个权值 $w_i$。
现在有 $q$ 个询问，每次询问 $x_l,x_r,y_l,y_r$，回答：
在 $[x_l,x_r] \times [y_l,y_r]$ 这个矩阵中，是否存在三个点，使得这三个点的权值能够形成一个三角形？
其中，$n,q \leq 10^5, x_i,y_i,w_i \in [1,10^9]$。
题解
首先给一个结论：
每次询问，只需要从矩阵中，取 $\log(10^9)$ 个点，就足够了。
证明：如果矩阵中，取了 $m>\log(10^9)$ 个点，仍然没找到三角形，那么，将这些点的权值进行排序：
$$w_1,w_2,w_3,w_4,w_5,…,w_m$$
我们可以得到 $w_1+w_2 < w_3$，那么 $2w_1 < w_3$，同理 $w_2+w_3<w_4$，那么 $2w_2<w_4$。
所以 $\forall i, 2w_i < w_{i+2}$，说明这个数组的元素是几何增长的，所以长度不可能超过 $\log(10^9)$。
于是每次询问，我们只要从中找到 $\log(10^9)$ 个点，怎么维护呢？
我们 $x$ 坐标用动态开点线段树维护，而每棵线段树里层维护一个 set，按照 $y$ 坐标的大小排序，这样可以通过 lower_bound() 来找到 $[y_l,y_r]$ 的。
线段树的层数为 $\log(10^9)$，而每个点最坏情况下都会在每一层出现，所以总时空复杂度就是 $O(n\log n * \log(10^9))$。
• 最后注意！这个题不能用二维线段树！
考虑一个例子：$[1,2] \times [1,2]$ 这个矩阵里刚好有 $4$ 个点 $(1,1),(1,2),(2,1),(2,2)$。
我们如果考虑 $x \in [1,2]$，那么这刚好对应一棵线段树，里面储存的是 $y \in [1,2]$ 的，但这棵线段树只能储存 $2$ 个值，所以会丢失一些信息！
代码
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+5;
const int N = 1e9;
struct Point {
int x, y, val;
bool operator<(const Point& others) const {
return y < others.y;
}
} a[maxn];
// 区间查询
// 单点修改
struct SegNode {
multiset<Point> s;
int lc, rc;
};
int cid = 0;
const int M = 80;
vector<Point> vec;
struct SegX {
SegNode tr[maxn*40];
void update(int& cur, int l, int r, int x, int y, int val) {
if (!cur) cur = ++cid;
tr[cur].s.insert(Point {x, y, val});
if (l == r) {
return;
}
int mid = (l+r) >> 1;
if (x <= mid) update(tr[cur].lc, l, mid, x, y, val);
if (x > mid) update(tr[cur].rc, mid+1, r, x, y, val);
}
void query(int cur, int l, int r, int xl, int xr, int yl, int yr) {
if (!cur) return;
if (vec.size() > M) return;
if (xl <= l && xr >= r) {
// 寻找 [yl, yr] 之间的
auto pl = tr[cur].s.lower_bound(Point {0, yl, 0});
auto pr = tr[cur].s.lower_bound(Point {0, yr+1, 0});
while (pl != pr) {
if (pl->y > yr) break;
vec.push_back(*pl);
if (vec.size() > M) return;
pl = next(pl);
}
return;
}
int mid = (l+r) >> 1;
if (xl <= mid) query(tr[cur].lc, l, mid, xl, xr, yl, yr);
if (xr > mid) query(tr[cur].rc, mid+1, r, xl, xr, yl, yr);
}
} tr;
int RT = 0;
void query(int xl, int xr, int yl, int yr) {
vec.clear();
tr.query(RT, 1, N, xl, xr, yl, yr);
}
void update(int x, int y, int val) {
tr.update(RT, 1, N, x, y, val);
}
int n,q;
int main() {
cin >> n >> q;
for (int i = 1; i <= n; i++) {
cin >> a[i].x >> a[i].y >> a[i].val;
update(a[i].x, a[i].y, a[i].val);
}
while (q--) {
int xl, yl, xr, yr; cin >> xl >> yl >> xr >> yr;
query(xl, xr, yl, yr);
int good = 0;
sort(vec.begin(), vec.end(), [](auto a, auto b) {
return a.val < b.val;
});
for (int i = 0; i < vec.size(); i++) {
if (i >= 2 && vec[i-2].val + vec[i-1].val > vec[i].val) {
good = 1;
break;
}
}
cout << good << "\n";
}
}