P7357 「PMOI-1」中位数题解

我不懂主席树，但是我会整体二分。

不妨先考虑没有修改的情况怎么做。

看到中位数有个著名的 trcik 就是二分转 。

不妨考虑二分 ，对于询问 判断是否存在一条中位数大于等于 的路径。

判断方法就是将小于 的数点权设置为 ,大于的权值设置成 。如果一条路径和的权值小于 ，那么这条路径的中位数一定大于 。

自然的，我们就会想要查询经过 且权值最小的路径。注意到 互相不为祖先，因此两个端点一定一个在 子树内，另一个在 子树内。

我们考虑使用树上差分算出一条路径的权值。显然两个端点的 LCA 显然就是 的 LCA，因此 LCA 处的贡献对于所有点对都是一样的。 令 表示构成以 为根的子树的点的集合， 表示点 到根节点上所有点的权值和，因此我们实际上要查询的就是

这可以通过在 子树内分别查询一次最大值得到，可以通过 dfn 转成区间问题用线段树维护。

接下来是多个询问的情况，我们发现瓶颈在于每次都要重新加入小于 的点导致复杂度爆炸。一种在线处理的方式是使用标记永久化加上可持久化线段树来实现避免重复加入。

但是我不会标记永久化。不过这题支持离线，因此我们可以把所有操作都离线下来，接下来通过整体二分来解决。

具体的做法就是首先加入小于 的元素，此时对所有元素检查答案是否大于等于 。用两个 std::vector 分别带着小于的和大于的询问。

带着大于的询问向着右侧递归，返回后撤销掉所有小于 的加入，再带着小于的询问向左侧递归。

具体的实现可以看代码。

可以证明每个数最多会被加入 和删除 次，单次复杂度 ，总共的复杂度就是 。

考虑加入修改操作。注意到修改的操作实际上只改变了最后一位，因此每个询问的答案最多会在 和 中浮动（因为小于 的数无论如何异或都是小于 的，大于 的数同理）。

因此，我们先将每个数除以 抹掉最后一位，用剩下的所有位求一边答案，也就是每个询问的 。接下来对于所有询问我们都只需要判断答案是 还是 即可。

我们将修改按照点权除以 分类，将询问按照 分类。

可以看出来，只有点权除以 为 的数才可能对这个询问产生贡献。我们首先按照 从小到大处理，处理到 时，所有更小的数的贡献都已经加入线段树了，此时我们按照时间顺序处理询问和修改，处理询问的时候看一下答案是不是大于等于 即可。处理完一个 的答案之后，不要忘记把所有最后答案等于 的数加入贡献。

▶

INFO 参考代码

#include <algorithm>
#include <cassert>
#include <iostream>
#include <numeric>
#include <vector>

using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
const uint npos = -1;

namespace data_structure {

struct segtree {
    struct info_t {
        int maxn;

        info_t(int _maxn = 0x3f3f3f3f) : maxn(_maxn) {}

        friend info_t operator+(const info_t &lhs, const info_t &rhs) {
            return std::min(lhs.maxn, rhs.maxn);
        }
    };

    using tag_t = int;

    friend info_t operator*(const tag_t &t, const info_t &x) {
        auto ret = x;
        ret.maxn += t;
        return ret;
    }

    uint n;

    struct node {
        info_t info;
        tag_t tag;

        node() : info(), tag() {}
    };

    std::vector<node> t;

    static constexpr uint lc(uint p) { return p * 2; }
    static constexpr uint rc(uint p) { return p * 2 + 1; }

    void update(uint p) { t[p].info = t[lc(p)].info + t[rc(p)].info; }
    void apply(uint p, tag_t tag) {
        t[p].tag = tag + t[p].tag;
        t[p].info = tag * t[p].info;
        return;
    }
    void spread(uint p) {
        apply(lc(p), t[p].tag);
        apply(rc(p), t[p].tag);

        t[p].tag = 0;
        return;
    }

    void set(uint pos, const info_t &val, uint p = 1, uint rl = 0,
             uint rr = npos) {

        if (rr == npos) {
            rr = n;
        }

        if (rl + 1 == rr) {
            t[p].info = val;
            return;
        }

        spread(p);
        uint mid = (rl + rr) / 2;

        if (pos < mid) {
            set(pos, val, lc(p), rl, mid);
        }
        else {
            set(pos, val, rc(p), mid, rr);
        }

        update(p);
    }

    info_t query(uint l, uint r, uint p = 1, uint rl = 0, uint rr = npos) {
        if (rr == npos) {
            rr = n;
        }

        if (l <= rl && rr <= r) {
            return t[p].info;
        }

        spread(p);
        uint mid = (rl + rr) / 2;

        info_t ret;
        if (l < mid) {
            ret = query(l, r, lc(p), rl, mid);
        }
        if (mid < r) {
            ret = ret + query(l, r, rc(p), mid, rr);
        }

        return ret;
    }

    void apply(uint l, uint r, tag_t tag, uint p = 1, uint rl = 0,
               uint rr = npos) {

        if (rr == npos) {
            rr = n;
        }
        if (l <= rl && rr <= r) {
            apply(p, tag);
            return;
        }

        spread(p);

        uint mid = (rl + rr) / 2;

        if (l < mid) {
            apply(l, r, tag, lc(p), rl, mid);
        }
        if (mid < r) {
            apply(l, r, tag, rc(p), mid, rr);
        }
        update(p);
    }

    void build(uint rl, uint rr, uint p) {
        t[p] = node();

        if (rl + 1 == rr) {
            return;
        }

        uint mid = (rl + rr) / 2;

        build(rl, mid, lc(p));
        build(mid, rr, rc(p));

        update(p);
        return;
    }

    void clear() { build(0, n, 1); }

    void resize(uint _n) {
        n = _n;
        t.resize(n * 4);
        clear();
    }
};

} // namespace data_structure

namespace solve {
#ifdef ONLINE_JUDGE
const uint V = 65536 + 5;
#else
const uint V = 15;
#endif
struct pbs {
    struct query {
        uint ul, ur, vl, vr, l, fal;
    };

    std::vector<uint> ans;
    std::vector<query> q;

    std::vector<std::vector<std::pair<uint, uint>>> nds;

    std::vector<uint> index;

    data_structure::segtree sgt;

    void parallel_bs(uint l, uint r, uint rl, uint rr) {
        if (l + 1 == r) {
            for (uint j = rl; j < rr; j++) {
                uint i = index[j];
                ans[i] = l;
            }
            return;
        }
        if (rl == rr) {
            return;
        }

        uint mid = (l + r) / 2;

        for (size_t i = l; i < mid; i++) {
            for (auto &&j : nds[i]) {
                sgt.apply(j.first, j.second, 2);
            }
        }

        auto x =
            std::partition(index.begin() + rl, index.begin() + rr,
                           [&](uint p) {
                               int umax = sgt.query(q[p].ul, q[p].ur).maxn;
                               int vmax = sgt.query(q[p].vl, q[p].vr).maxn;

                               int lca = sgt.query(q[p].l, q[p].l + 1).maxn;
                               int fla = 0;

                               if (q[p].fal != npos) {
                                   fla = sgt.query(q[p].fal, q[p].fal + 1).maxn;
                               }

                               return umax + vmax - lca - fla > 0;
                           }) -
            index.begin();

        parallel_bs(mid, r, x, rr);

        for (size_t i = l; i < mid; i++) {
            for (auto &&j : nds[i]) {
                sgt.apply(j.first, j.second, -2);
            }
        }

        parallel_bs(l, mid, rl, x);

        return;
    }

    pbs(uint n, const std::vector<int> &v) : ans(n), q(n), nds(V), sgt() {
        sgt.resize(v.size());

        for (size_t i = 0; i < v.size(); i++) {
            sgt.set(i, {v[i]});
        }

        return;
    }
};

struct tree {
    struct node {
        uint dfn, sz;
        uint top;
        uint depth;
    };
    std::vector<node> t;
    std::vector<std::vector<uint>> e;
    std::vector<bool> vis;

    std::vector<uint> fa;

    void dfs(uint p) {
        vis[p] = true;
        t[p].sz = 1;
        std::vector<uint> re;
        for (auto &&i : e[p]) {
            if (vis[i]) {
                fa[p] = i;
                continue;
            }
            t[i].depth = t[p].depth + 1;
            re.emplace_back(i);
            dfs(i);
            t[p].sz += t[i].sz;
        }
        e[p] = re;
        std::sort(e[p].begin(), e[p].end(),
                  [&](uint x, uint y) { return t[x].sz > t[y].sz; });
        return;
    }

    uint nxt = 0;

    void cal_top(uint p, uint top) {
        t[p].dfn = nxt++;

        t[p].top = top;

        if (e[p].empty()) {
            return;
        }

        cal_top(e[p][0], top);

        for (size_t i = 1; i < e[p].size(); i++) {
            cal_top(e[p][i], e[p][i]);
        }

        return;
    }

    uint lca(uint u, uint v) {
        while (t[u].top != t[v].top) {
            if (t[t[u].top].depth < t[t[v].top].depth) {
                std::swap(u, v);
            }
            u = t[u].top;
            u = fa[u];
        }

        if (t[u].depth < t[v].depth) {
            std::swap(u, v);
        }

        return v;
    }

    tree(uint n) : t(n), e(n), vis(n), fa(n) {}
};

struct solver {
    struct qu {
        uint u, v;
        uint time;

        uint ind;
    };

    void solve() {
        uint n, q;
        std::cin >> n >> q;

        std::vector<uint> val(n);
        tree t(n);

        for (size_t i = 0; i < n; i++) {
            std::cin >> val[i];
        }

        for (size_t i = 0; i < n - 1; i++) {
            uint u, v;
            std::cin >> u >> v;
            --u, --v;

            t.e[u].emplace_back(v);
            t.e[v].emplace_back(u);
        }

        std::vector<qu> query;
        std::vector<std::pair<uint, uint>> modify;

        for (uint i = 0; i < q; i++) {
            uint op;
            std::cin >> op;

            --op;
            if (op) {
                uint u, v;
                std::cin >> u >> v;
                --u, --v;

                query.emplace_back(u, v, i, (uint)query.size());
            }
            else {
                uint x;
                std::cin >> x;
                --x;
                modify.emplace_back(x, i);
            }
        }

        t.dfs(0);
        t.cal_top(0, 0);

        std::vector<int> ival(n);

        for (size_t i = 0; i < n; i++) {
            ival[t.t[i].dfn] = -(int(t.t[i].depth) + 1);
        }

        pbs pbins(query.size(), ival);

        for (size_t i = 0; i < query.size(); i++) {
            auto u = query[i].u, v = query[i].v;

            pbins.q[i].vl = t.t[v].dfn;
            pbins.q[i].vr = t.t[v].dfn + t.t[v].sz;

            pbins.q[i].ul = t.t[u].dfn;
            pbins.q[i].ur = t.t[u].dfn + t.t[u].sz;

            uint l = t.lca(u, v);

            pbins.q[i].l = t.t[l].dfn;

            if (l == 0) {
                pbins.q[i].fal = npos;
            }
            else {
                pbins.q[i].fal = t.t[t.fa[l]].dfn;
            }
        }

        for (size_t i = 0; i < n; i++) {
            pbins.nds[val[i] / 2].emplace_back(t.t[i].dfn,
                                               t.t[i].dfn + t.t[i].sz);
        }

        std::vector<uint> init(query.size());
        std::iota(init.begin(), init.end(), 0);

        pbins.index = init;
        pbins.parallel_bs(0, V, 0, init.size());

        auto ans = pbins.ans;

        std::vector<std::pair<uint, uint>> v(n);
        for (size_t i = 0; i < n; i++) {
            v[i].second = i;
            v[i].first = val[i];
        }

        std::sort(v.begin(), v.end());
        std::sort(query.begin(), query.end(),
                  [&](const qu &lhs, const qu &rhs) {
                      return std::make_pair(ans[lhs.ind], lhs.time) <
                             std::make_pair(ans[rhs.ind], rhs.time);
                  });

        std::sort(modify.begin(), modify.end(),
                  [&](const std::pair<uint, uint> &lhs,
                      const std::pair<uint, uint> &rhs) {
                      return std::make_pair(val[lhs.first] / 2, lhs.second) <
                             std::make_pair(val[rhs.first] / 2, rhs.second);
                  });

        uint ptr_nodes = 0;
        uint ptr_modify = 0;

        data_structure::segtree sgt;
        sgt.resize(n);

        for (size_t i = 0; i < n; i++) {
            sgt.set(i, {ival[i]});
        }

        uint prev_val = npos;
        uint prev_ptr = 0;

        for (auto &&i : query) {
            uint cur_val = ans[i.ind] * 2 + 1;

            if (cur_val != prev_val) {
                while (prev_ptr < ptr_nodes) {
                    auto cur = v[prev_ptr].second;

                    auto l = t.t[cur].dfn, r = t.t[cur].dfn + t.t[cur].sz;

                    if (val[cur] == prev_val) {
                        sgt.apply(l, r, 2);
                    }
                    ++prev_ptr;
                }
                prev_val = cur_val;
            }

            while (ptr_nodes < v.size() && v[ptr_nodes].first <= cur_val) {
                auto cur = v[ptr_nodes].second;

                auto l = t.t[cur].dfn, r = t.t[cur].dfn + t.t[cur].sz;

                if (v[ptr_nodes].first < cur_val) {
                    sgt.apply(l, r, 2);
                }
                ++ptr_nodes;
            }
            while (ptr_modify < modify.size() &&
                   val[modify[ptr_modify].first] <= cur_val &&
                   (val[modify[ptr_modify].first] / 2 < cur_val / 2 ||
                    modify[ptr_modify].second < i.time)) {
                uint cur = modify[ptr_modify].first;
                uint prev = val[cur];
                val[cur] ^= 1;

                int detla = (val[cur] < cur_val) - (prev < cur_val);

                auto l = t.t[cur].dfn, r = t.t[cur].dfn + t.t[cur].sz;
                sgt.apply(l, r, detla * 2);
                ++ptr_modify;
            }

            int umax = sgt.query(pbins.q[i.ind].ul, pbins.q[i.ind].ur).maxn;
            int vmax = sgt.query(pbins.q[i.ind].vl, pbins.q[i.ind].vr).maxn;

            int lca = sgt.query(pbins.q[i.ind].l, pbins.q[i.ind].l + 1).maxn;
            int fla = 0;

            if (pbins.q[i.ind].fal != npos) {
                fla =
                    sgt.query(pbins.q[i.ind].fal, pbins.q[i.ind].fal + 1).maxn;
            }

            ans[i.ind] *= 2;

            if (umax + vmax - lca - fla <= 0) {
                ans[i.ind]++;
            }
        }

        for (size_t i = 0; i < query.size(); i++) {
            std::cout << ans[i] << "\n";
        }
    }
};

} // namespace solve

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    solve::solver slv;
    slv.solve();
    std::cout << std::flush;
    return 0;
}