原题链接
题意:在一张n x m的网格中,左上角是(1,1),右下角是(n,n)。从(1,1)开始,只能往下或往右移动,在某些点上有地雷,不能移动到有地雷的点上,且不能移动出边界,求可能到达的点的数量。
分析:当某个点的上方和左边都不可到达时,该点不可到达,并会对该点下方和右边的点造成影响。考虑从上往下对每行排序后的地雷进行处理。对于每个地雷(x,y),找到(x-1,y+1)开始的从左往右不可到达的范围,那么x这行的这个范围也不可到达。对一行可以用线段树实现区间查询和覆盖,只需用滚动数组维护该行和上一行的线段树即可。每一行处理完后查询该行可以到达的点数,累加后得到答案。
#include <bits/stdc++.h> using namespace std; #define ls(x) (x << 1) #define rs(x) (x << 1 | 1) const int inf = 0x3f3f3f3f; const int N = 100005; int n, m, k; int tr[2][N << 2], lz[2][N << 2]; long long ans; vector<int> v[N]; void push_down(int f, int x, int l, int r, int mid) { if (lz[f][x] == -1) return ; tr[f][ls(x)] = (mid - l + 1) * lz[f][x]; tr[f][rs(x)] = (r - mid) * lz[f][x]; lz[f][ls(x)] = lz[f][rs(x)] = lz[f][x]; lz[f][x] = -1; } void update(int f, int x, int l, int r, int L, int R, int v) { if (L <= l && R >= r) { tr[f][x] = (r - l + 1) * v; lz[f][x] = v; return ; } int mid = (l + r) >> 1; push_down(f, x, l, r, mid); if (L <= mid) update(f, ls(x), l, mid, L, R, v); if (R > mid) update(f, rs(x), mid + 1, r, L, R, v); tr[f][x] = tr[f][ls(x)] + tr[f][rs(x)]; } int query(int f, int x, int l, int r, int L, int R) { if (!tr[f][x]) return inf; if (l == r) return l; int mid = (l + r) >> 1; push_down(f, x, l, r, mid); if (L <= l && R >= r) { if (tr[f][ls(x)]) return query(f, ls(x), l, mid, L, R); else return query(f, rs(x), mid + 1, r, L, R); } else { if (R <= mid) return query(f, ls(x), l, mid, L, R); else if (L > mid) return query(f, rs(x), mid + 1, r, L, R); else return min(query(f, ls(x), l, mid, L, R), query(f, rs(x), mid + 1, r, L, R)); } } int main() { int t; scanf("%d", &t); while (t--) { scanf("%d%d%d", &n, &m, &k); for (int i = 0; i <= n; i++) v[i].clear(); memset(tr, 0, sizeof tr); memset(lz, -1, sizeof lz); while (k--) { int x, y; scanf("%d%d", &x, &y); v[x].push_back(y); } ans = 0; update(0, 1, 1, m, 1, 1, 1); for (int i = 1; i <= n; i++) { sort(v[i].begin(), v[i].end()); int l = 0; for (auto &j : v[i]) { if (l + 1 <= j - 1) { int pos = query((i & 1) ^ 1, 1, 1, m, l + 1, j - 1); if (pos != inf) update(i & 1, 1, 1, m, pos, j - 1, 1); } l = j; } if (l + 1 <= m) { int pos = query((i & 1) ^ 1, 1, 1, m, l + 1, m); if (pos != inf) update(i & 1, 1, 1, m, pos, m, 1); } ans += tr[i & 1][1]; update((i & 1) ^ 1, 1, 1, m, 1, m, 0); } printf("%lld\n", ans); } return 0; }