1 条题解

  • 4
    @ 2021-10-2 7:29:32

    在我的个人博客中阅读

    Statement

    给定一棵 nn 个点的树,每个节点上均有一个二进制运算符(&|^)和一个在 [0, 2k1][0,~2^k-1] 之间的数值。

    接下来给定 mm 个操作,每个操作分为两类:

    • 修改某个结点上的运算符与数值。
    • 给定 x, y, zx,~y,~z,你可以先任意指定一个值 val[0, z]val \in [0,~z],然后在树上沿 xxyy 之间的简单路径从 xxyy 移动,每次到达一个结点后将 valval 变为 val op[i] a[i]val~op[i]~a[i]op[i]op[i] 为该节点上运算符,a[i]a[i] 为该节点上数值。最大化到达 yy 结点时的 valval 值并输出。

    n, m105, 0k64n,~m \le 10^5,~0 \le k \le 64

    Solution

    由于询问时询问的是树上两点间路径的信息,不难想到通过树链剖分将每条路径转化为 logn\log n 个区间。

    由于每个结点上的运算符均为二进制位运算符,运算过程中不同二进制位之间互不影响。我们可以考虑对于每一个二进制位分开来考虑其运算结果,即对于每一个二进制位都求出其为 0/10/1 时经过路径后的结果,最后通过类似数位 DP 的计算方法即可求出 [0, z][0,~z] 区间内的初值可产生的最大运算结果。

    而由于询问时两点间的路径是有向的,从 xlcax \to lca 的路径是向上的,从 lcaylca \to y 的路径是向下的。将树上移动的顺序对应到区间上移动的顺序,不难发现 xlcax \to lca 的路径对应的区间都是从右向左经过的,lcaylca \to y 的路径对应的区间都是从左向右经过的。因此我们需要对于每一个区间都求出每一个二进制位初始为 0/10/1 时从左向右或是从右向左经过该区间之后的值。

    考虑如何维护,建立一棵线段树,每个线段树结点都记录 l0[i], l1[i], r0[i], r1[i]l0[i],~l1[i],~r0[i],~r1[i] 分别表示:

    • 二进制第 ii 位为 00 时从左向右经过该区间后该位的值。
    • 二进制第 ii 位为 11 时从左向右经过该区间后该位的值。
    • 二进制第 ii 位为 00 时从右向左经过该区间后该位的值。
    • 二进制第 ii 位为 11 时从右向左经过该区间后该位的值。

    每次合并两个结点 a, ba,~b 的信息时令:

    • ans.l0[i] = a.l0[i] && b.l1[i] || !a.l0[i] && b.l0[i]
    • ans.l1[i] = a.l1[i] && b.l1[i] || !a.l1[i] && b.l0[i]
    • ans.r0[i] = b.r0[i] && a.r1[i] || !b.r0[i] && a.r0[i]
    • ans.r1[i] = b.r1[i] && a.r1[i] || !b.r1[i] && a.r0[i]

    即枚举某一位在经过第一个区间后的值,将其以初值代入第二个区间得到结果。

    此时对于每一个询问我们将路径拆为 logn\log n 个区间,每个区间对应 logn\log n 个线段树结点,每次合并结点需要花费 O(k)O(k) 的时间,因此此时的总时间复杂度为 O(m×k×log2n)O(m \times k \times \log ^2n),无法通过本题。

    Optimization

    我们仔细分析上面的时间复杂度,发现两个 logn\log n 在该算法中都难以去除,因此我们考虑优化掉 O(k)O(k) 的时间复杂度。容易发现 O(k)O(k) 的时间复杂度来自线段数结点合并。

    仔细观察我们发现对于 kk 位分别进行逻辑运算是非常浪费的,我们考虑将四个大小为 kk 的数组压为四个大小为 2k2^k 的数字,将逻辑运算转变为二进制位运算即可。对应的四个转移变为:

    • ans.l0 = (a.l0 & b.l1) | (~a.l0 & b.l0)
    • ans.l1 = (a.l1 & b.l1) | (~a.l1 & b.l0)
    • ans.r0 = (b.r0 & a.r1) | (~b.r0 & a.r0)
    • ans.r1 = (b.r1 & a.r1) | (~b.r1 & a.r0)

    因此合并结点信息的复杂度优化到 O(1)O(1),总复杂度达到 O(m×log2n)O(m \times \log ^2n),足以通过此题。

    Code

    View on GitHub

    Code
    /**
     * @author Macesuted (i@macesuted.moe)
     * @copyright Copyright (c) 2021
     * @brief 
     *      My Solution: https://macesuted.moe/article/h1034
     */
    
    #include <bits/stdc++.h>
    using namespace std;
    
    namespace io {
    #define SIZE (1 << 20)
    char ibuf[SIZE], *iS, *iT, obuf[SIZE], *oS = obuf, *oT = oS + SIZE - 1, c, qu[55];
    int f, qr;
    inline void flush(void) { return fwrite(obuf, 1, oS - obuf, stdout), oS = obuf, void(); }
    inline char getch(void) { return (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, SIZE, stdin), (iS == iT ? EOF : *iS++)) : *iS++); }
    inline void putch(char x) {
        *oS++ = x;
        if (oS == oT) flush();
        return;
    }
    string getstr(void) {
        string s = "";
        char c = getch();
        while (c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == EOF) c = getch();
        while (!(c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == EOF)) s.push_back(c), c = getch();
        return s;
    }
    void putstr(string str, int begin = 0, int end = -1) {
        if (end == -1) end = str.size();
        for (register int i = begin; i < end; i++) putch(str[i]);
        return;
    }
    template <typename T>
    inline T read() {
        register T x = 0;
        for (f = 1, c = getch(); c < '0' || c > '9'; c = getch())
            if (c == '-') f = -1;
        for (x = 0; c <= '9' && c >= '0'; c = getch()) x = x * 10 + (c & 15);
        return x * f;
    }
    template <typename T>
    inline void write(const T& t) {
        register T x = t;
        if (!x) putch('0');
        if (x < 0) putch('-'), x = -x;
        while (x) qu[++qr] = x % 10 + '0', x /= 10;
        while (qr) putch(qu[qr--]);
        return;
    }
    struct Flusher_ {
        ~Flusher_() { flush(); }
    } io_flusher_;
    }  // namespace io
    using io::getch;
    using io::getstr;
    using io::putch;
    using io::putstr;
    using io::read;
    using io::write;
    
    #define maxn 100005
    
    class SegmentTree {
       public:
        struct Node {
            unsigned long long l0, l1, r0, r1;
            Node(void) { l0 = 0, l1 = ~0, r0 = 0, r1 = ~0; }
            Node operator+(const Node& b) const {
                Node a = *this, ans;
                ans.l0 = (a.l0 & b.l1) | (~a.l0 & b.l0);
                ans.l1 = (a.l1 & b.l1) | (~a.l1 & b.l0);
                ans.r0 = (b.r0 & a.r1) | (~b.r0 & a.r0);
                ans.r1 = (b.r1 & a.r1) | (~b.r1 & a.r0);
                return ans;
            }
        };
        Node tree[maxn << 2];
        int n;
    
        void update(int p, int l, int r, int qp, int opt, unsigned long long val) {
            if (l == r) {
                if (opt == 1)
                    tree[p].l0 = tree[p].r0 = 0, tree[p].l1 = tree[p].r1 = val;
                else if (opt == 2)
                    tree[p].l0 = tree[p].r0 = val, tree[p].l1 = tree[p].r1 = ~0;
                else
                    tree[p].l0 = tree[p].r0 = val, tree[p].l1 = tree[p].r1 = ~val;
                return;
            }
            int mid = (l + r) >> 1;
            qp <= mid ? update(p << 1, l, mid, qp, opt, val) : update(p << 1 | 1, mid + 1, r, qp, opt, val);
            tree[p] = tree[p << 1] + tree[p << 1 | 1];
            return;
        }
        Node merge(int p, int l, int r, int ql, int qr) {
            if (ql <= l && r <= qr) return tree[p];
            int mid = (l + r) >> 1;
            Node answer;
            if (ql <= mid) answer = answer + merge(p << 1, l, mid, ql, qr);
            if (qr > mid) answer = answer + merge(p << 1 | 1, mid + 1, r, ql, qr);
            return answer;
        }
        inline void resize(int tn) { return n = tn, void(); }
        inline void update(int p, int opt, unsigned long long val) { return update(1, 1, n, p, opt, val); }
        inline Node merge(int l, int r) { return merge(1, 1, n, l, r); }
    };
    
    SegmentTree tree;
    
    int opt[maxn];
    unsigned long long val[maxn];
    
    vector<vector<int> > graph;
    
    int dep[maxn], siz[maxn], son[maxn], top[maxn], fa[maxn], dfn[maxn];
    
    void dfs1(int p, int pre = 0) {
        dep[p] = dep[pre] + 1, fa[p] = pre, siz[p] = 1;
        for (vector<int>::iterator i = graph[p].begin(); i != graph[p].end(); i++)
            if (*i != pre) {
                dfs1(*i, p);
                if (!son[p] || siz[*i] > siz[son[p]]) son[p] = *i;
                siz[p] += siz[*i];
            }
        return;
    }
    int tim = 0;
    void dfs2(int p, int t) {
        dfn[p] = ++tim, top[p] = t;
        if (son[p]) dfs2(son[p], t);
        for (vector<int>::iterator i = graph[p].begin(); i != graph[p].end(); i++)
            if (*i != fa[p] && *i != son[p]) dfs2(*i, *i);
        return;
    }
    int lca(int x, int y) {
        while (top[x] != top[y]) {
            if (dep[top[x]] < dep[top[y]]) swap(x, y);
            x = fa[top[x]];
        }
        return dep[x] < dep[y] ? x : y;
    }
    
    int main() {
        int n = read<int>(), m = read<int>(), k = read<int>();
        graph.resize(n + 1);
        for (register int i = 1; i <= n; i++) opt[i] = read<int>(), val[i] = read<unsigned long long>();
        for (register int i = 1, from, to; i < n; i++) {
            from = read<int>(), to = read<int>();
            graph[from].push_back(to), graph[to].push_back(from);
        }
        dfs1(1), dfs2(1, 1);
        tree.resize(n);
        for (register int i = 1; i <= n; i++) tree.update(dfn[i], opt[i], val[i]);
        while (m--)
            if (read<int>() == 1) {
                int x = read<int>(), y = read<int>(), t = lca(x, y);
                unsigned long long z = read<unsigned long long>();
                SegmentTree::Node record1, record2;
                while (top[x] != top[t]) record1 = tree.merge(dfn[top[x]], dfn[x]) + record1, x = fa[top[x]];
                record1 = tree.merge(dfn[t], dfn[x]) + record1;
                while (top[y] != top[t]) record2 = tree.merge(dfn[top[y]], dfn[y]) + record2, y = fa[top[y]];
                if (y != t) record2 = tree.merge(dfn[t] + 1, dfn[y]) + record2;
                swap(record1.l0, record1.r0), swap(record1.l1, record1.r1);
                SegmentTree::Node record = record1 + record2;
                bool up = true;
                unsigned long long answer = 0;
                for (register int i = k - 1; ~i; i--) {
                    unsigned long long l0 = (record.l0 >> i & 1), l1 = (record.l1 >> i & 1), t = (z >> i & 1);
                    if (!up)
                        answer |= max(l0, l1) << i;
                    else if (t == 0)
                        answer |= l0 << i;
                    else if (l0 >= l1)
                        answer |= l0 << i, up = false;
                    else
                        answer |= l1 << i;
                }
                cout << answer << endl;
            } else {
                int p = read<int>(), opt = read<int>();
                unsigned long long val = read<unsigned long long>();
                tree.update(dfn[p], opt, val);
            }
        return 0;
    }
    
    • 1

    信息

    ID
    200
    时间
    250ms
    内存
    128MiB
    难度
    6
    标签
    (无)
    递交数
    70
    已通过
    22
    上传者