F - Robots and Exits
\(n\) 个人，\(m\) 个出口在一条数轴上，坐标是正整数。你每次可以让所有人向左或向右一步，人在某个出口上后就离开。求多少种操作的方案使得人全部走光。两个方案相同当且仅当存在至少一个人在两次操作序列进行完成后从不同的出口消失。对 \(10^9+7\) 取模。
\(1\le n,m\le 10^5.\)
妙妙题。把每个点抽象成一个二维点 \((a_i,b_i)\)，横坐标是到左边出口的距离，纵坐标是到右边出口的距离。当 \(a_i<a_j,b_i>b_j\) 的时候，假设 \(i\) 从右边出去，则 \(j\) 也一定从右边出去，左侧同理。把左右走抽象成一条折线，在 \((x,y)\) 这个位置代表从起点出发，最远的左侧点距离为 \(x\) 右侧为 \(y\)。把坐标向右上平移 \(0.5\) 个单位，那么折线下方的点都去右边，上方都去左边。假设我们已经确定了一个去右边的集合且满足上述性质，则一定可以找到一条满足条件的斜线。故我们可以直接dp，\(f_j=\sum\limits_{a_i<a_j,b_i<b_j}f_i+1\)，这是个二维偏序问题，树状数组优化即可。
#include <bits/stdc++.h>
const int maxn = 1e5 + 5, mod = 1e9 + 7;
int qmod(int x) {
if (x >= mod) {
x -= mod;
}
return x;
}
int n, m, x[maxn], y[maxn], tot, tmp[maxn], cnt, f[maxn], c[maxn], ans;
std :: pair<int, int> p[maxn];
void add(int x, int v) {
while (x <= cnt) {
c[x] = qmod(c[x] + v);
x += x & -x;
}
}
int ask(int x) {
int ret = 0;
while (x) {
ret = qmod(ret + c[x]);
x -= x & -x;
}
return ret;
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) scanf("%d", x + i);
for (int i = 1; i <= m; i++) scanf("%d", y + i);
for (int i = 1; i <= n; i++) {
int r = std :: lower_bound(y + 1, y + 1 + m, x[i]) - y;
if (r > 1 && r <= m) p[++tot] = {x[i] - y[r - 1], y[r] - x[i]};
}
for (int i = 1; i <= tot; i++) tmp[i] = p[i].second;
std :: sort(tmp + 1, tmp + 1 + tot);
cnt = std :: unique(tmp + 1, tmp + 1 + tot) - tmp - 1;
for (int i = 1; i <= tot; i++) {
p[i].second = std :: lower_bound(tmp + 1, tmp + 1 + cnt, p[i].second) - tmp;
}
std :: sort(p + 1, p + 1 + tot, [&](std :: pair<int, int> a, std :: pair<int, int> b){
if (a.first != b.first) return a.first < b.first;
return a.second > b.second;
});
for (int i = 1; i <= tot; i++) {
if (p[i].first == p[i - 1].first && p[i].second == p[i - 1].second) continue;
f[i] = qmod(ask(p[i].second - 1) + 1);
ans = qmod(ans + f[i]);
add(p[i].second, f[i]);
}
printf("%d\n", qmod(ans + 1));
return 0;
}