P9447 题解【2024qd 互测 T3】

· · 题解

设 dis_{i, j} 表示两点环上的距离。

将整个过程倒过来考虑。设 f_i 表示从 s 的无穷远处最终走到 i 号射线的答案。显然有 |f_i-f_j|\leq dis_{i, j}。

由外向内依次加入桥。初始没有桥，f_i=dis_{i, s}。当加入一座桥时，设其两端为 a,b，则交换 f_a,f_b。

此时可能不满足上面给出的不等式，因此需要更新一下。发现对于 f_a,f_b，只需要使用相邻的位置更新即可，否则一定存在更多不合法位置。

此后，再用 f_a,f_b 向外更新。问题转化为区间对公差 \pm 1 的等差数列取 \min，线段树维护即可。时间复杂度 \mathcal O(m\log nm+n)。

int n, m, s; pii a[MAXM];

struct setr {
    #define STZ MAXN << 2
    int tag1[STZ], tag2[STZ];

    il void pushdown(int x, int l, int r) {
        int mid = l + r >> 1;
        if (tag1[x] != inf) {
            gmin(tag1[ls(x)], tag1[x]);
            gmin(tag1[rs(x)], tag1[x] + mid - l + 1);
            tag1[x] = inf;
        }
        if (tag2[x] != inf) {
            gmin(tag2[ls(x)], tag2[x]);
            gmin(tag2[rs(x)], tag2[x] - (mid - l + 1));
            tag2[x] = inf;
        }
    }

    il void build(int x, int l, int r) {
        tag1[x] = tag2[x] = inf;
        if (l == r) return tag1[x] = tag2[x] = l == s ? 0 : inf, void();
        int mid = l + r >> 1;
        build(ls(x), l, mid); build(rs(x), mid + 1, r);
    }

    il int query(int x, int l, int r, int k) {
        if (l == r) return min(tag1[x], tag2[x]);
        int mid = l + r >> 1; pushdown(x, l, r);
        return k <= mid ? query(ls(x), l, mid, k) : query(rs(x), mid + 1, r, k);
    }

    il void upd1(int x, int l, int r, int ql, int qr, int &k) {
        if (l > qr || r < ql) return;
        if (l >= ql && r <= qr) return gmin(tag1[x], k), k += r - l + 1, void();
        int mid = l + r >> 1; pushdown(x, l, r);
        upd1(ls(x), l, mid, ql, qr, k); upd1(rs(x), mid + 1, r, ql, qr, k);
    }

    il void upd2(int x, int l, int r, int ql, int qr, int &k) {
        if (l > qr || r < ql) return;
        if (l >= ql && r <= qr) return gmin(tag2[x], k), k -= r - l + 1, void();
        int mid = l + r >> 1; pushdown(x, l, r);
        upd2(ls(x), l, mid, ql, qr, k); upd2(rs(x), mid + 1, r, ql, qr, k);
    }

    il void print(int x, int l, int r) {
        if (l == r) return printf("%d\n", min(tag1[x], tag2[x])), void();
        int mid = l + r >> 1; pushdown(x, l, r);
        print(ls(x), l, mid); print(rs(x), mid + 1, r);
    }

    il void update(int x, int l, int r, int k, int p) {
        if (l == r) return gmin(tag1[x], p), gmin(tag2[x], p);
        int mid = l + r >> 1; pushdown(x, l, r);
        k <= mid ? update(ls(x), l, mid, k, p) : update(rs(x), mid + 1, r, k, p);
    }

    il void update2(int x, int l, int r, int k, int p) {
        if (l == r) return tag1[x] = tag2[x] = p, void();
        int mid = l + r >> 1; pushdown(x, l, r);
        k <= mid ? update2(ls(x), l, mid, k, p) : update2(rs(x), mid + 1, r, k, p);
    }
} T;

il void change(int x) {
    T.update(1, 1, n, x, min(T.query(1, 1, n, x % n + 1), T.query(1, 1, n, x > 1 ? x - 1 : n)) + 1);
}

il void spread(int x) {
    int g, f = T.query(1, 1, n, x);
    T.upd1(1, 1, n, 1, x - 1, g = f + n - x + 1); T.upd1(1, 1, n, x + 1, n, g = f + 1);
    T.upd2(1, 1, n, 1, x - 1, g = f + x - 1); T.upd2(1, 1, n, x + 1, n, g = f + n - 1);
}

int main() {
    read(n, m, s); rer(i, 1, m, a);
    sort(a + 1, a + 1 + m, greater<>());
    T.build(1, 1, n); spread(s);
    rep1(i, 1, m) {
        int x = a[i].snd, y = x % n + 1, fx = T.query(1, 1, n, x), fy = T.query(1, 1, n, y);
        T.update2(1, 1, n, y, fx); T.update2(1, 1, n, x, fy);
        change(x); change(y); spread(x); spread(y);
    } T.print(1, 1, n);
    return 0;
}