CF793F Julia the snail 题解

题意

有一个长为 \(n\) 的杆，上面有 \(m\) 条绳子，每条绳子可以让蜗牛从 \(l_i\) 爬到 \(r_i\)（中途不能离开），保证 \(r_i\) 各不相同。蜗牛也可以自然下落。

现在有 \(q\) 次询问，询问 \(x\) 出发，途中高度不能低于 \(x\) 或高于 \(y\)，问最高能爬到的位置。

\(n,m,q\leq 10^5\)。

题解

模拟赛 T4，加强了数据范围，改为了 \(n,m,q\leq 10^6\)，卡掉了分块做法。

我们考虑将询问离线。因为题目中明确不同绳子的 \(r_i\) 互不相同，所以我们考虑按询问的右端点去处理，维护当前左端点的答案。换句话说，我们使用当前处理的区间的右端点 \(r\) 去遍历，并维护所有满足 \(l \in \left[1,r\right]\) 的区间 \(\left[l,r\right]\) 的答案。

考虑我们移动了右端点 \(r\)，即 \(r - 1 \rightarrow r\)，可以发现只有存在右端点为 \(r\) 的绳子，那么答案才会产生相应的影响。那么我们考虑存在右端点为 \(r\) 的绳子，考虑其对答案的影响，我们设这条绳子的左端点为 \(l\)，设对于\(x \in \left[1,r\right]\)，\(ans_x\) 为左端点为 \(x\)，右端点为 \(r\) 的区间的询问的答案。也就是从 \(x\) 出发，只使用当前已经添加了的绳子，可以爬到的最高高度。我们考虑添加绳子对答案的影响，如果 \(x > l\)，根据题意，由于其只能使用包含在区间 \(\left[x,r\right]\) 内的绳子，所以这条绳子不会对这部分左端点的答案产生影响。对于 \(x \le l\)，若 \(ans_x < l\)，由于蜗牛无法爬到这条绳子的最低点，所以也不会产生影响。所以这条绳子只对满足 \(x \in \left[1,l\right] \land ans_x \ge l\) 的左端点产生影响，不难看出会把这部分左端点的答案直接更新为 \(r\)。

考虑使用数据结构维护对答案的影响，我们需要一个数据结构支持将一定区间内大于等于给定值的部分更新为一个新的更大的值。可以想到吉司机线段树可以满足这个需求，实现更改。具体实现的话我们可以对于每个线段树节点维护最大值 \(max_i\) 和次大值 \(sec_i\)，对于每次更改，可以表达为四元组 \(\left(l, r, A, B\right)\) 的形式，即将区间 \(\left[l,r\right]\) 的大于等于 \(A\) 的部分更新为 \(B\)。对于更改的时候，如果 \(max_i < A\)，那么这个区间的值不会被更新，如果 \(max_i \ge A > sec_i\)，那么只更新最大值即可，如果 \(sec_i \ge A\)，那么递归地处理。在 \(n,m,q\) 同阶的情况下，总复杂度为 \(\mathcal{O}(n \log n)\)。

复杂度分析

这部分是笔者自己对吉司机线段树的理解，如有错误欢迎各位指正。

考虑所有满足 \(a_i \neq a_{i + 1}\) 的点对 \(\left(i, i + 1\right)\)，如果我们的更改操作递归到了叶子节点，那么这样的点对便会减少一个，可以看出每消除一个这样的点对复杂度均为 \(\mathcal{O}(\log n)\)，初始状态下这样的点对有 \(\mathcal{O}(n)\) 个（线段树初始化时 \(ans_x \leftarrow x\)），考虑每次更改对点对数量的影响，可以看出最多会增加两个点对 \(\left(l - 1,l\right)\) 和 \(\left(r, r + 1\right)\)，所以总共出现过的的点对数量为 \(\mathcal{O}(n + q)\)，又因为消除每个点对的复杂度均为 \(\mathcal{O}(\log n)\)，所以对于操作的三种情况中最后一种情况的复杂度为 \(\mathcal{O}(n \log n)\)，其他情况和单点查询的复杂度同普通线段树，故总复杂度为 \(\mathcal{O}(n \log n)\)。

Code

//D
#include <bits/stdc++.h>

typedef int valueType;
typedef std::vector<valueType> ValueVector;

constexpr valueType MIN = INT_MIN;

class SegmentBeats {
public:
    typedef ValueVector container;

private:
    valueType N;

    container max, second, tagA, tagB;

    void addTag(valueType id, valueType A, valueType B) {
        if (max[id] >= A && max[id] <= B) {
            max[id] = std::max(max[id], B); //TAG

            if (tagA[id] == MIN) //TAG
                tagA[id] = A;

            tagB[id] = B;
        }
    }

    void pushDown(valueType id) {
        if (tagA[id] != MIN) {
            addTag(id << 1, tagA[id], tagB[id]);
            addTag(id << 1 | 1, tagA[id], tagB[id]);

            tagA[id] = tagB[id] = MIN;
        }
    }

    void update(valueType id, valueType key) {
        if (key > max[id]) {
            second[id] = max[id];
            max[id] = key;
        } else if (key < max[id] && key > second[id]) {
            second[id] = key;
        }
    }

    void pushUp(valueType id) {
        max[id] = MIN;
        second[id] = MIN;

        update(id, max[id << 1]);
        update(id, second[id << 1]);
        update(id, max[id << 1 | 1]);
        update(id, second[id << 1 | 1]);
    }

public:
    explicit SegmentBeats(valueType size) : N(size), max((N << 2) + 5, MIN), second((N << 2) + 5, MIN),
                                            tagA((N << 2) + 5, MIN), tagB((N << 2) + 5, MIN) {
        build(1, 1, N);
    }

    void modify(valueType L, valueType R, valueType A, valueType B) {
        modify(1, 1, N, L, R, A, B);
    }

    valueType query(valueType pos) {
        return query(1, 1, N, pos);
    }

private:
    void build(valueType id, valueType L, valueType R) {
        if (L == R) {
            max[id] = L;
            return;
        }

        valueType mid = (L + R) >> 1;

        build(id << 1, L, mid);
        build(id << 1 | 1, mid + 1, R);

        pushUp(id);
    }

    void modify(valueType id, valueType nodeL, valueType nodeR, valueType queryL, valueType queryR, valueType A,
                valueType B) {
        if (max[id] < A)
            return;

        if (nodeL >= queryL && nodeR <= queryR && second[id] < A) {
            addTag(id, A, B);

            return;
        }

        pushDown(id);

        valueType mid = (nodeL + nodeR) >> 1;

        if (queryL <= mid)
            modify(id << 1, nodeL, mid, queryL, queryR, A, B);

        if (queryR > mid)
            modify(id << 1 | 1, mid + 1, nodeR, queryL, queryR, A, B);

        pushUp(id);
    }

    valueType query(valueType id, valueType nodeL, valueType nodeR, valueType pos) {
        if (nodeL == nodeR)
            return max[id];

        pushDown(id);

        valueType mid = (nodeL + nodeR) >> 1;

        if (pos <= mid)
            return query(id << 1, nodeL, mid, pos);
        else
            return query(id << 1 | 1, mid + 1, nodeR, pos);
    }
};

struct Query {
    valueType left;
    valueType id;

    Query() = default;

    Query(valueType left, valueType id) : left(left), id(id) {};
};

int main() {
    std::ios_base::sync_with_stdio(false);

    valueType N, M;

    std::cin >> N >> M;

    ValueVector rope(N + 1, 0);

    for (valueType i = 0; i < M; ++i) {
        valueType left, right;

        std::cin >> left >> right;

        rope[right] = left;
    }

    SegmentBeats tree(N);

    valueType Q;

    std::cin >> Q;

    std::vector<std::vector<Query>> query(N + 1);

    for (valueType i = 0; i < Q; ++i) {
        valueType left, right;

        std::cin >> left >> right;

        query[right].emplace_back(left, i);
    }

    ValueVector ans(Q);

    for (valueType i = 1; i <= N; ++i) {
        valueType left = rope[i];
        valueType right = i;

        if (left > 0)
            tree.modify(1, left, left, right);


        for (auto const &iter: query[right])
            ans[iter.id] = tree.query(iter.left);
    }

    for (auto const &iter: ans)
        std::cout << iter << '\n';

    return 0;
}