自动搬运

查看原文

来自洛谷，原作者为

	Lskkkno1 We should try our best to reach for the summit.

搬运于2025-08-24 22:22:15，当前版本为作者最后更新于2020-06-02 21:23:57，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

• 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;
}