移动

移动

题意

有一个 \(n\times m\) 的网格图，有 \(k\) 个点不能走。

每次移动可以向右或向下走，只能走两次。

求能走到的点的个数。

思路

可以发现只能是从第一排向下走或从第一列向右走。

统计上下走能到的点和左右走能到的点，减去重复的即可。

扫描 \(x\)，使用线段树维护 \(y\) 每一个位置能否被上下走到。

初始第一行时，从 \(1\) 到第一个不能走的点的左边都赋成 \(1\)，其他设为 \(0\)。

扫描每一行时，若有一个点不能走，把它设为 \(0\)，其它不变，继承上一行。

这样就维护好了上下走的情况，答案先加上线段树里 \(1\) 的个数（其实就是区间求和）。

容易发现左右走只会走到最左边的不能走的格子的左边。

答案加上这些格子的数量，减去这些格子中在线段树里已经为 \(1\) 的个数（重复的）。

注意扫描到第一列最靠上的不能走的位置时，它和下面的行就不能左右走了。因为 \((1,1)\) 没法走到它们。

代码

#include <bits/stdc++.h>
#define ll long long
using namespace std;

template <typename T>
void read(T& x) {
	x = 0; T f = 1;
	char ch = getchar();
	while (ch < '0' || ch > '9') {
		if (ch == '-') f = -f;
		ch = getchar();
	}
	while (ch >= '0' && ch <= '9') {
		x = x * 10 + ch - '0';
		ch = getchar();
	}
	x = x * f;
}

const int N = 2e5 + 5;

struct segt {
	struct node {
		int l, r;
		int cnt, tag;
	} t[N << 2];
	#define ls (p << 1)
	#define rs (p << 1 | 1)
	void build(int p, int l, int r) {
		t[p].tag = -1, t[p].l = l, t[p].r = r;
		if (l == r) return ;
		int mid = (l + r) >> 1;
		build(ls, l, mid);
		build(rs, mid + 1, r);
	}
	void make(int p, int v) {
		t[p].tag = v;
		t[p].cnt = v * (t[p].r - t[p].l + 1);
	}
	void push_down(int p) {
		if (t[p].tag != -1) {
			make(ls, t[p].tag);
			make(rs, t[p].tag);
			t[p].tag = -1; 
		}
	}
	void modify(int p, int l, int r, int v) {
		if (l <= t[p].l && t[p].r <= r) {
			make(p, v);
			return ;
		}
		push_down(p);
		if (l <= t[ls].r) modify(ls, l, r, v);
		if (r >= t[rs].l) modify(rs, l, r, v);
		t[p].cnt = t[ls].cnt + t[rs].cnt; 
	}
	int query(int p, int l, int r) {
		if (l <= t[p].l && t[p].r <= r) {
			return t[p].cnt;
		}
		push_down(p);
		int res = 0;
		if (l <= t[ls].r) res += query(ls, l, r);
		if (r >= t[rs].l) res += query(rs, l, r);
		return res;
	}
} T;

int n, m, k, Min[N];
struct point {
	int x, y;
} a[N];
vector <int> v[N];
ll ans;

int main() {
	read(n); read(m); read(k);
	for (int i = 1; i <= n; i ++) Min[i] = m + 1;
	int minx = 1e9;
	for (int i = 1; i <= k; i ++) {
		read(a[i].x); 
		read(a[i].y);
		Min[a[i].x] = min(Min[a[i].x], a[i].y);
		v[a[i].x].push_back(a[i].y);
		if (a[i].y == 1) minx = min(minx, a[i].x);
	}
	T.build(1, 1, m);
	T.modify(1, 1, Min[1] - 1, 1);
	ans += Min[1] - 1; 
	for (int i = 2; i <= n; i ++) {
		for (auto y : v[i]) T.modify(1, y, y, 0);
		ans += T.query(1, 1, m);
		if (Min[i] != 1 && i < minx) // i < minx 注意
			ans += Min[i] - 1 - T.query(1, 1, Min[i] - 1);
	}
	cout << ans << "\n";
	return 0;
}