ARC101F Robots and Exits 题解

ARC101F Robots and Exits

题意

• 数轴上有 $n$ 个 A 类点 $A_i$，$m$ 个 B 类点 $B_j$，任意两点的坐标都是整数且互不相同。
• 每次操作可以让所有 A 类点同时向左或者向右移动一个单位。
• 如果在某个时刻 $A_i$ 与 $B_j$ 重合，则将 $a_i$ 赋值为 $j$，同时 $A_i$ 立刻消失。
• 当所有 A 类点都消失时不再操作，求此时序列 $a$ 的方案数。
• $n,m \le 10^5$，答案对 $10^9+7$ 取模。

题解

首先把最左边的 B 类点左边的 A 类点去掉，最右边的 B 类点右边的 A 类点去掉，这些点完全不影响答案。

对于剩下的 A 类点，设 $A_i$ 与其左边最近的 B 类点的距离为 $x_i$，与其右边最近的 B 类点的距离为 $y_i$，将 $(x_i,y_i)$ 放到平面直角坐标系中。

可以发现题目要求的方案数等于从原点开始画一条单调递增的曲线将这些点划分成两个集合的方案数（不妨设这条曲线不过任何一个点）。这是因为对于每一条曲线，若其先到达 $x_i$ 则意味着 $A_i$ 与左边的 B 类点重合，否则先到达 $y_i$ 则意味着 $A_i$ 与右边的 B 类点重合。

接下来就是计数了，显然考虑 DP。要做到不重不漏，考虑将曲线的每一段拉直，使曲线在任意一个横坐标上的位置尽可能往下。这样曲线变成了若干段折线，且每个从往上改变方向为往右的位置都是某个点所在的位置。

考虑 DP 这个点，设 $f_i$ 表示在点 $i$ 从往上改变方向为往右时的方案数，有转移 $f_{i} = 1 + \sum_{x_j < x_i,y_j < y_i} f_j$，显然可以树状数组优化。

最终的答案为 $1 + \sum f_i$，总时间复杂度 $\mathcal O(n \log n)$。

代码

const int N = 1e5 + 7;
int n, m, a[N], b[N], x[N], y[N], X[N], Y[N], p[N], t;
struct BIT {
	vector<modint> c;
	inline BIT() {}
	inline BIT(int n) { c.resize(n); }
	inline void add(ui x, modint k) {
		while (x < c.size()) c[x] += k, x += x & -x;
	}
	inline modint ask(ui x) {
		modint k = 0;
		while (x) k += c[x], x -= x & -x;
		return k;
	}
};

int main() {
	rd(n), rd(m), rda(a, n), rda(b, m);
	for (int i = 1; i <= n; i++) {
		if (a[i] < b[1] || a[i] > b[m]) continue;
		int p = upper_bound(b + 1, b + m + 1, a[i]) - b;
		x[++t] = a[i] - b[p-1], y[t] = b[p] - a[i], ::p[t] = t;
		X[t] = x[t], Y[t] = y[t];
	}
	sort(X + 1, X + t + 1), sort(Y + 1, Y + t + 1);
	int u = unique(X + 1, X + t + 1) - X - 1;
	int v = unique(Y + 1, Y + t + 1) - Y - 1;
	for (int i = 1; i <= t; i++)
		x[i] = lower_bound(X + 1, X + u + 1, x[i]) - X,
		y[i] = lower_bound(Y + 1, Y + v + 1, y[i]) - Y;
	sort(p + 1, p + t + 1, [&](int i, int j) {
		return x[i] == x[j] ? y[i] > y[j] : x[i] < x[j];
	});
	t = unique(p + 1, p + t + 1, [&](int i, int j) {
		return x[i] == x[j] && y[i] == y[j];
	}) - p - 1;
	BIT c(v + 1);
	modint ans = 1, now;
	for (int i = 1; i <= t; i++)
		ans += now = c.ask(y[p[i]] - 1) + 1, c.add(y[p[i]], now);
	print(ans);
	return 0;
}