제출 #613647

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
613647		KoD	Birthday gift (IZhO18_treearray)	C++17	100 / 100	791 ms	98780 KiB

treearray

#include <bits/stdc++.h>

using std::vector;
using std::array;
using std::pair;
using std::tuple;

template <class F> struct fixed : private F {
    explicit fixed(F&& f) : F(std::forward<F>(f)) {}
    template <class... Args> decltype(auto) operator()(Args&&... args) const {
        return F::operator()(*this, std::forward<Args>(args)...);
    }
};

constexpr int LOG = 20;

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int N, M, Q;
    std::cin >> N >> M >> Q;
    vector<vector<int>> graph(N);
    for (int i = 0; i < N - 1; ++i) {
        int a, b;
        std::cin >> a >> b;
        a -= 1;
        b -= 1;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }

    vector<int> in(N), out(N), depth(N), tour;
    tour.reserve(2 * N - 2);
    fixed([&](auto&& dfs, const int u, const int p) -> void {
        in[u] = (int)tour.size();
        tour.push_back(u);
        for (const int v : graph[u]) {
            if (v != p) {
                depth[v] = depth[u] + 1;
                dfs(v, u);
                tour.push_back(u);
            }
        }
        out[u] = (int)tour.size();
    })(0, -1);

    const auto select = [&](const int i, const int j) {
        return depth[i] < depth[j] ? i : j;
    };
    array<vector<int>, LOG> table = {};
    table[0] = tour;
    for (int d = 0; d + 1 < LOG; ++d) {
        const int n = std::max(0, (int)table[d].size() - (1 << d));
        table[d + 1].resize(n);
        for (int i = 0; i < n; ++i) {
            table[d + 1][i] = select(table[d][i], table[d][i + (1 << d)]);
        }
    }
    const auto lca = [&](const int u, const int v) {
        const int l = std::min(in[u], in[v]);
        const int r = std::max(out[u], out[v]);
        const int t = 31 - __builtin_clz(r - l);
        return select(table[t][l], table[t][r - (1 << t)]);
    };

    vector<std::set<int>> one(N), two(N);
    vector<int> A(M), B(M - 1);
    for (int i = 0; i < M; ++i) {
        std::cin >> A[i];
        A[i] -= 1;
        one[A[i]].insert(i);
    }
    for (int i = 0; i < M - 1; ++i) {
        B[i] = lca(A[i], A[i + 1]);
        two[B[i]].insert(i);
    }
    const auto find = [&](const std::set<int>& set, const int l, const int r) {
        const auto itr = set.lower_bound(l);
        return (itr != set.end() and *itr < r) ? *itr : -1;
    };

    while (Q--) {
        int t;
        std::cin >> t;
        if (t == 1) {
            int p, v;
            std::cin >> p >> v;
            p -= 1;
            v -= 1;
            one[A[p]].erase(p);
            A[p] = v;
            one[A[p]].insert(p);
            if (p > 0) {
                two[B[p - 1]].erase(p - 1);
                B[p - 1] = lca(A[p - 1], A[p]);
                two[B[p - 1]].insert(p - 1);
            }
            if (p + 1 < M) {
                two[B[p]].erase(p);
                B[p] = lca(A[p], A[p + 1]);
                two[B[p]].insert(p);
            }
        } else {
            int l, r, v;
            std::cin >> l >> r >> v;
            l -= 1;
            v -= 1;
            if (const int t = find(one[v], l, r); t != -1) {
                std::cout << t + 1 << ' ' << t + 1 << '\n';
            } else if (const int t = find(two[v], l, r - 1); t != -1) {
                std::cout << t + 1 << ' ' << t + 2 << '\n';
            } else {
                std::cout << -1 << ' ' << -1 << '\n';
            }
        }
    }
    return 0;
}

/*
5 4 4
1 2
3 1
3 4
5 3
4 5 2 3
2 1 3 1
1 3 5
2 3 4 5
2 1 3 1
*/

• Subtask 1: 12 / 12
• Subtask 2: 18 / 18
• Subtask 3: 26 / 26
• Subtask 4: 44 / 44