题解 P6592 [YsOI2020] 幼儿园

· · 题解

题目描述

给定一个有向图。

每次询问从点 x 开始走，只能经过编号在 [l, r] 的边，且走的边的编号单调递减，是否可以走到 1 号点。

强制在线。

正解

这里提供一个贪心 + 线段树的做法，跑得还挺快的。

前置信息

按照套路建反图，现在问题变成从 1 号点出发，走的边的编号单调递增，是否可以走到 x 。

可以将一条路径抽象看做是数轴上 [l, r] 的线段，询问就是看给定的区间 [l_q, r_q] 是否包含了一条线段（即路径）。

由于问题强制在线，所以要考虑把从 1 号点到每个 x 点的一些有用的路径 [l, r] 给预处理出来。

"有用的路径" 是什么意思呢？

如果固定了走的最大边为 r，那么走最小边 l 肯定越大越好，l 更小的路径就没用了。

有一个比较有用的性质是：有用的路径不超过 m 条（在后面会有证明），于是可以全部预处理出来。

进入正题

从小往大枚举每一条边，这样子更新一系列的信息是没有后效性的。

设 f_x 为从 1 号点到 x 号点的一条路径，最小边编号 l 最大可以是多少。

假设现在枚举的一条边是 u \to v，编号为 i。

这条边只会影响到点 v（不会影响到其他点），

因为当前从 v 号点再往其他点走，是走不动的，其他边的编号都小于它。

而之后的路径也不会用到这条边去更新其他点，新的路径的 r 一定大于等于 i。

这条边只会多生成一条从 1 到 v 的有用的路径，即 : 从之前 1 到 f_u 走的路径加上 u \to v 这一条边，表示成线段是 [f_u, i]。

并将 f_v 对 f_u 取 \max。

特别的，如果 u 是一号点，直接将 f_v 赋值为当前枚举边的编号，如果 v 是 1 号点，不进行任何操作。

现在知道了所有有用的路径，询问就是一个简单的二维偏序问题（l_q \le l ,~~ r \le r_q）。

对于每一个点 x，用动态开点的线段树维护左端点 l 在 [l_q, r_q] 中 ，右端点的最小值，判断其是否小于 r_q 即可。

时间复杂度 O(n \log n)。

代码

#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 5;

int n, m, q, w;
int f[N];

int ll, rr, cv, vcnt;
int root[N];
struct node {
    int lch, rch, val;
} a[N * 30];

void modify(int &u, int l, int r) {
    if(!u) u = ++vcnt, a[u].val = N;
    if(l == r) return a[u].val = min(a[u].val, cv), void();
    int mid = (l + r) >> 1;
    if(ll <= mid) modify(a[u].lch, l, mid);
    else modify(a[u].rch, mid + 1, r);
    a[u].val = min(a[a[u].lch].val, a[a[u].rch].val);
}
int query(int u, int l, int r) {
    if(!u || (ll <= l && r <= rr)) return a[u].val;
    int mid = (l + r) >> 1;
    if(rr <= mid) return query(a[u].lch, l, mid);
    else if(mid < ll) return query(a[u].rch, mid + 1, r);
    else return min(query(a[u].lch, l, mid), query(a[u].rch, mid + 1, r));
}

inline int read() {
    int x = 0; char ch = getchar();
    while(!isdigit(ch)) ch = getchar();
    while(isdigit(ch)) x = x * 10 + ch - '0', ch = getchar();
    return x;
}

int main() {
    //freopen("b.in", "r", stdin);
    //freopen("b.out", "w", stdout);
    n = read(), m = read(), q = read(), w = read();
    memset(f, -1, sizeof f);
    f[1] = 0;
    a[0].val = N;
    for(int i = 1, u, v; i <= m; ++i) { // 反边单调递增
        v = read(), u = read();
        if(~f[u]) {
            f[v] = max(f[v], u == 1 ? i : f[u]);
            ll = rr = f[v], cv = i;
            modify(root[v], 1, m);
        }
    }
    int L = 0;
    for(int Case = 1, x, l, r; Case <= q; ++Case) {
        x = read(), l = read(), r = read();
        if(w) x ^= L, l ^= L, r ^= L;
        if(x == 1) {
            puts("1"), ++L;
            continue;
        }
        ll = l, rr = m;
        int rMin = query(root[x], 1, m);
        if(rMin <= r) {
            puts("1"), ++L;
            continue;
        } else {
            puts("0");
        }
    }
    return 0;
}