[AGC015E] Mr.Aoki Incubator

一个咕了很久的题。

做法

为了方便描述做法,把题目中的操作称为感染。

可以注意到,假设初始只有一个人被感染了,那么任何时刻被感染的所有人在坐标轴上是连续的一段(即使不存在两个被感染的人中间有一个没有被感染的人。

经过充分长的时间后,所有人在坐标轴上的位置按照速度排列。这也就是说,一个人初始被感染,最终能感染的人是一个速度区间内的所有人。

所以我们只要求出每个人能感染的速度区间,然后做 DP 数有多少种选法能覆盖所有人就能求出方案数。

现在来考虑怎么求这个区间。对于第 \(i\) 个人,他自己和他前面速度最快的人一定被感染,设这个人速度为 \(v_1\),他自己和他后面速度最慢的人一定被感染,设这个人速度为 \(v_2\)

因为我们把他自己算进去了,所以必然有 \(v_1 \ge v_2\)。速度在 \([v_2, v_1]\) 中的人全部被感染了。我们来检验一下剩下的人是否可能被感染。首先看在他左边的,速度小于 \(v_2\) 的人。这个人永远不可能和第 \(i\) 个人以及第 \(i\) 个人右边的人有接触,假设这个人被感染了,如果他是被自己左边的人感染的,那么左边这个人在感染的时候必然已经跑到了他右边,不可能会感染他;如果他是被自己右边的人(但是在第 \(i\) 个人左边)感染的,那么感染他的人速度比他慢,我们可以通过同样的分析得到这个人也只可能被他右边的人感染,这样一直推下去,必然会得出矛盾。右边速度大于 \(v_1\) 的人同理不会被感染。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
#include <bits/stdc++.h>

using namespace std;

const int maxn = 200010;

int n = 0;

int mn[maxn], mx[maxn], tag[maxn];
vector<int> rig[maxn];

struct P {
int x, v;
P(int x_=0, int v_=0) : x(x_), v(v_) {}
} px[maxn], pv[maxn];

bool cmpx(const P &p1, const P &p2) {
return p1.x < p2.x;
}

bool cmpv(const P &p1, const P &p2) {
return p1.v < p2.v;
}

const int mod = 1e9 + 7;

int sum[maxn << 2];

void build(int l, int r, int rt) {
tag[rt] = 1;
if (l == r) return;
int m = (l + r) >> 1;
build(l, m, rt<<1);
build(m+1, r, rt<<1|1);
sum[rt] = (sum[rt<<1] + sum[rt<<1|1]) % mod;
}

void modify(int rt, int v) {
tag[rt] = 1LL * tag[rt] * v % mod;
sum[rt] = 1LL * sum[rt] * v % mod;
}

void pushDown(int rt) {
if (tag[rt] != 1) {
modify(rt<<1, tag[rt]);
modify(rt<<1|1, tag[rt]);
tag[rt] = 1;
}
}

void upd_add(int p, int v, int l, int r, int rt) {
if (l == r) {
sum[rt] = (sum[rt] + v) % mod;
return;
}
pushDown(rt);
int m = (l + r) >> 1;
if (p <= m) upd_add(p, v, l, m, rt<<1);
else upd_add(p, v, m+1, r, rt<<1|1);
sum[rt] = (sum[rt<<1] + sum[rt<<1|1]) % mod;
}

void upd_mod(int p, int v, int l, int r, int rt) {
if (l == r) {
sum[rt] = v;
return;
}
pushDown(rt);
int m = (l + r) >> 1;
if (p <= m) upd_mod(p, v, l, m, rt<<1);
else upd_mod(p, v, m+1, r, rt<<1|1);
sum[rt] = (sum[rt<<1] + sum[rt<<1|1]) % mod;
}

int ask(int L, int R, int l, int r, int rt) {
if (L <= l && r <= R) return sum[rt];
int m = (l + r) >> 1;
int ret = 0;
pushDown(rt);
if (L <= m) ret = (ret + ask(L, R, l, m, rt<<1)) % mod;
if (R > m) ret = (ret + ask(L, R, m+1, r, rt<<1|1)) % mod;
return ret;
}

void upd_mul(int L, int R, int x, int l, int r, int rt) {
if (L <= l && r <= R) {
modify(rt, x);
return;
}
int m = (l + r) >> 1;
pushDown(rt);
if (L <= m) upd_mul(L, R, x, l, m, rt<<1);
if (R > m) upd_mul(L, R, x, m+1, r, rt<<1|1);
sum[rt] = (sum[rt << 1] + sum[rt << 1 | 1]) % mod;
}

int main() {
scanf("%d", &n);
build(1, n, 1);
for (int i = 1; i <= n; i++) {
scanf("%d%d", &px[i].x, &px[i].v);
pv[i] = px[i];
}
sort(px + 1, px + n + 1, cmpx);
sort(pv + 1, pv + n + 1, cmpv);
mx[0] = -0x3f3f3f3f, mn[n+1] = 0x3f3f3f3f;
for (int i = 1; i <= n; i++)
mx[i] = max(mx[i-1], px[i].v);
for (int i = n; i >= 1; i--)
mn[i] = min(mn[i+1], px[i].v);
for (int i = 1; i <= n; i++) {
int l = mn[i], r = mx[i];
l = int (lower_bound(pv + 1, pv + n + 1, P(0, l), cmpv) - pv);
r = int (lower_bound(pv + 1, pv + n + 1, P(0, r), cmpv) - pv);
rig[l].push_back(r);
}
upd_add(0, 1, 0, n, 1);
for (int i = 1; i <= n; i++) {
for (int j = 0; j < rig[i].size(); j++) {
int r = rig[i][j];
int s = ask(0, r-1, 0, n, 1);
upd_mul(r, n, 2, 0, n, 1);
upd_add(r, s, 0, n, 1);
}
upd_mod(i-1, 0, 0, n, 1);
}
int ans = ask(n, n, 0, n, 1);
printf("%d\n", ans);
return 0;
}