CF1583G Omkar and Time Travel
想清楚了就不难。
首先我们考察一下性质，一次 time leap 之后只有包含于 \((a_i, b_i)\) 的区间会被重置，考虑这样一件事情：设 \(f_{l,r}\) 表示从 \(l\) 左边走到 \(r\) 右边的 time leap 次数。那么转移是简单的。
这个 dp 感觉是很有用的，看一下有什么用。考察如何到达最终状态，不难发现是每次走到当前的最大值，然后变成子问题缩小规模，那么可以维护出当前 \((l,r)\) 这个区间内的任务还没有完成，答案就是若干个 \(f_{l,r}\) 相加的形式。具体是哪些可以对 \(s\) 排序后求出。
这时候状态数是 \(O(n^2)\) 的，考虑优化，不妨重新设 \(f_i\) 表示从第 \(i\) 个区间右端点做了一次 time leap 后把中间的任务重新完成所需的次数，那么就有：
\[f_i = \sum_{I(j) \subseteq I(i)} f_j + 1
\]
其中 \(I(x)\) 表示 \(x\) 对于的区间。那么这个就可以扫描线 + 树状数组维护了。我们原来的那个 dp 可以看做区间内的 \(f\) 相加，这样就转化为了二维偏序问题，可以直接做到 \(O(n \log n)\)。
const int P = 1e9 + 7;
void add(int &x, int y) {
(x += y) >= P ? x -= P : 0;
}
const int N = 2e5 + 10;
int n;
struct Travel {
int a, b, id;
}a[N];
int f[N], r[N];
int t, s[N];
int q[N << 1];
struct BIT {
int tr[N << 1];
int lowbit(int x) {
return x & -x;
}
void add(int x, int y) {
for(; x; x -= lowbit(x))
::add(tr[x], y);
}
int query(int x) {
int res = 0;
for(; x <= 2 * n; x += lowbit(x))
::add(res, tr[x]);
return res;
}
void clear() {
for(int i = 1; i <= 2 * n; ++i)
tr[i] = 0;
}
}seg;
int main() {
read(n);
for(int i = 1; i <= n; ++i)
read(a[i].a, a[i].b), a[i].id = i;
sort(a + 1, a + n + 1, [](Travel x, Travel y) {
return x.b < y.b;
});
for(int i = 1; i <= n; ++i)
r[a[i].id] = i;
for(int i = 1; i <= n; ++i) {
f[i] = seg.query(a[i].a) + 1;
seg.add(a[i].a, f[i]);
}
read(t);
priority_queue<pair<int, int>> que;
for(int i = 1; i <= t; ++i) {
read(s[i]), s[i] = r[s[i]];
que.push(make_pair(a[s[i]].b, a[s[i]].a));
}
int cur = 1;
while(que.size()) {
while(que.size() && que.top().second < cur)
que.pop();
if(!que.size()) break;
auto u = que.top(); que.pop();
q[u.first - 1] = cur, cur = u.second;
}
int ans = 0;
seg.clear();
for(int i = 1, j = 1; i <= 2 * n; ++i) {
if(a[j].b == i) seg.add(a[j].a, f[j]), j++;
if(q[i]) add(ans, seg.query(q[i]) + 1);
}
printf("%d\n",ans);
}