제출 #953286

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
953286		makrav	Tourism (JOI23_tourism)	C++14	100 / 100	1548 ms	200328 KiB

tourism

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

#define pb push_back
#define all(a) (a).begin(), (a).end()
#define ff first 
#define sz(x) (int)(x).size()
#define sc second

struct fenwick {
    int n;
    vector<int> t;
    fenwick() = default;
    fenwick(int n_) {
        n = n_;
        t.assign(n + 1, 0);
    }

    void clear() {
        t.assign(n + 1, 0);
    }

    int sum(int x) {
        int ans = 0;
        for (int i = x; i >= 0; i = (i & (i + 1)) - 1) {
            ans += t[i];
        }
        return ans;
    }

    void upd(int pos, int delta) {
        for (int i = pos; i < n; i = i | (i + 1)) {
            t[i] += delta;
        }
    }
};

int sp[18][200010];

signed main() {
    ios_base::sync_with_stdio(false);
    cout.tie(nullptr);
    vector<int> Log2(200010);
    for (int i = 2; i < 200010; i++) {
        Log2[i] = Log2[i / 2] + 1;
    }

    int n, m, q; cin >> n >> m >> q;
    vector<vector<int>> g(n);
    for (int i = 0; i < n - 1; i++) {
        int u, v; cin >> u >> v;
        u--; v--;
        g[u].pb(v);
        g[v].pb(u);
    }

    vector<vector<int>> num(n);
    vector<int> c(m);
    for (int i = 0; i < m; i++) {
        cin >> c[i];
        c[i]--;
        num[c[i]].pb(i);
    }
    vector<pair<int, int>> segs;
    vector<vector<int>> evs;
    vector<set<int>> sub(n);
    unordered_map<ll, int> pos;
    vector<int> h(n), siz(n);

    auto convert = [&](int l, int r) -> ll {
        return l * 1ll * m + r;
    };

    vector<int> htl, vtl, ppos(n);

    auto dfs = [&](int v, int p, auto&&dfs) -> void {
        htl.pb(h[v]);
        vtl.pb(v);
        ppos[v] = sz(vtl) - 1;
        siz[v] = sz(num[v]);
        vector<int> sons;
        for (auto &u : g[v]) {
            if (u != p) {
                h[u] = h[v] + 1;
                sons.pb(u);
                dfs(u, v, dfs);
                htl.pb(h[v]);
                vtl.pb(v);
                siz[v] += siz[u];
            }
        }
        auto add_ev = [&](int l, int r) {
            if (pos.find(convert(l, r)) == pos.end()) {
                pos[convert(l, r)] = sz(segs);
                segs.pb({ l, r });
                evs.pb({});
            }
            if (l == 0 && r == m - 1) {
                evs[pos[convert(l, r)]].pb(h[v]);
                evs[pos[convert(l, r)]].pb(h[v] - 1);
                return;
            }
            evs[pos[convert(l, r)]].pb(h[v]);
            };
        if (sons.empty()) {
            if (num[v].empty()) {
                add_ev(0, m - 1);
                return;
            }
            sub[v].insert(num[v][0]);
            segs.pb({0, num[v][0] - 1});
            evs.pb({h[v]});
            pos[convert(0, num[v][0] - 1)] = sz(segs) - 1;
            segs.pb({num[v][0] + 1, m - 1});
            pos[convert(num[v][0] + 1, m - 1)] = sz(segs) - 1;
            evs.pb({h[v]});
            for (int j = 1; j < sz(num[v]); j++) {
                int el = num[v][j];
                auto it = sub[v].lower_bound(el);
                if (it == sub[v].end()) {
                    int lst = (*sub[v].rbegin());
                    add_ev(lst + 1, m - 1);
                    add_ev(lst + 1, el - 1);
                    add_ev(el + 1, m - 1);
                }
                else if (it == sub[v].begin()) {
                    int bg = *it;
                    add_ev(0, bg - 1);
                    add_ev(el + 1, bg - 1);
                    add_ev(0, el - 1);
                }
                else {
                    int nxt = *it;
                    it--;
                    int pr = *it;
                    add_ev(pr + 1, nxt - 1);
                    add_ev(pr + 1, el - 1);
                    add_ev(el + 1, nxt - 1);
                }
                sub[v].insert(el);
            }
            return;
        }
        int maxson = sons[0];
        for (int i = 1; i < sz(sons); i++) {
            if (siz[sons[i]] > siz[maxson]) maxson = sons[i];
        }
        swap(sub[v], sub[maxson]);
        if (sz(sub[v]) == 0) {
            if (num[v].empty()) {
                add_ev(0, m - 1);
                return;
            }
            sub[v].insert(num[v][0]);
            segs.pb({ 0, num[v][0] - 1 });
            evs.pb({ h[v] });
            pos[convert(0, num[v][0] - 1)] = sz(segs) - 1;
            segs.pb({ num[v][0] + 1, m - 1 });
            pos[convert(num[v][0] + 1, m - 1)] = sz(segs) - 1;
            evs.pb({ h[v] });
            for (int j = 1; j < sz(num[v]); j++) {
                int el = num[v][j];
                auto it = sub[v].lower_bound(el);
                if (it == sub[v].end()) {
                    int lst = (*sub[v].rbegin());
                    add_ev(lst + 1, m - 1);
                    add_ev(lst + 1, el - 1);
                    add_ev(el + 1, m - 1);
                }
                else if (it == sub[v].begin()) {
                    int bg = *it;
                    add_ev(0, bg - 1);
                    add_ev(el + 1, bg - 1);
                    add_ev(0, el - 1);
                }
                else {
                    int nxt = *it;
                    it--;
                    int pr = *it;
                    add_ev(pr + 1, nxt - 1);
                    add_ev(pr + 1, el - 1);
                    add_ev(el + 1, nxt - 1);
                }
                sub[v].insert(el);
            }
            return;
        }
        

        for (int son : sons) {
            if (son != maxson) {
                int num = 0, prev = -1;
                for (int el : sub[son]) {
                    if (num == 0) {
                        add_ev(0, el - 1);
                    }
                    if (num == sz(sub[son]) - 1) {
                        add_ev(el + 1, m - 1);
                    }
                    if (num > 0) {
                        add_ev(prev + 1, el - 1);
                    }
                    prev = el;
                    num++;
                }
                for (int el : sub[son]) {
                    auto it = sub[v].lower_bound(el);
                    if (it == sub[v].end()) {
                        int lst = (*sub[v].rbegin());
                        add_ev(lst + 1, m - 1);
                        add_ev(lst + 1, el - 1);
                        add_ev(el + 1, m - 1);
                    } else if (it == sub[v].begin()) {
                        int bg = *it;
                        add_ev(0, bg - 1);
                        add_ev(el + 1, bg - 1);
                        add_ev(0, el - 1);
                    } else {
                        int nxt = *it;
                        it--;
                        int pr = *it;
                        add_ev(pr + 1, nxt - 1);
                        add_ev(pr + 1, el - 1);
                        add_ev(el + 1, nxt - 1);
                    }
                    sub[v].insert(el);
                }
                sub[son].clear();
            }
        }
        if (!num[v].empty()) {
            for (int el : num[v]) {
                auto it = sub[v].lower_bound(el);
                if (it == sub[v].end()) {
                    int lst = (*sub[v].rbegin());
                    add_ev(lst + 1, m - 1);
                    add_ev(lst + 1, el - 1);
                    add_ev(el + 1, m - 1);
                }
                else if (it == sub[v].begin()) {
                    int bg = *it;
                    add_ev(0, bg - 1);
                    add_ev(el + 1, bg - 1);
                    add_ev(0, el - 1);
                }
                else {
                    int nxt = *it;
                    it--;
                    int pr = *it;
                    add_ev(pr + 1, nxt - 1);
                    add_ev(pr + 1, el - 1);
                    add_ev(el + 1, nxt - 1);
                }
                sub[v].insert(el);
            }
        }
    };
    dfs(0, 0, dfs);
    for (int i = 0; i < sz(vtl); i++) {
        sp[0][i] = i;
    }
    auto comp = [&](int i, int j) {
        return (htl[i] < htl[j] ? i : j);
    };
    for (int pw = 1; pw < 18; pw++) {
        for (int i = 0; i + (1 << pw) - 1 < sz(vtl); i++) {
            sp[pw][i] = comp(sp[pw - 1][i], sp[pw - 1][i + (1 << (pw - 1))]);
        }
    }
    auto get = [&](int l, int r) {
        if (l > r) swap(l, r);
        int lg = Log2[r - l + 1];
        return comp(sp[lg][l], sp[lg][r - (1 << lg) + 1]);
    };

    auto lca = [&](int v, int u) {
        if (v == -1) return u;
        if (u == -1) return v;
        return vtl[get(ppos[v], ppos[u])];
    };

    vector<int> t(4 * m);
    auto build = [&](int v, int tl, int tr, auto&&build) -> void {
        if (tl + 1 == tr) {
            t[v] = c[tl];
            return;
        }
        int tm = (tl + tr) / 2;
        build(v * 2, tl, tm, build);
        build(v * 2 + 1, tm, tr, build);
        t[v] = lca(t[v * 2], t[v * 2 + 1]);
    };  

    auto getlca = [&](int v, int tl, int tr, int l, int r, auto&&getlca) {
        if (l <= tl && tr <= r) { return t[v]; }
        if (tl >= r || tr <= l) {
            return -1;
        }
        int tm = (tl + tr) / 2;
        return lca(getlca(v * 2, tl, tm, l, r, getlca), getlca(v * 2 + 1, tm, tr, l, r, getlca));
    };
    
    build(1, 0, m, build);
    vector<vector<pair<int, int>>> reqs(m), segss(m);
    vector<pair<int, int>> qrs(q);
    vector<int> cntt(sz(segs));
    for (int i = 0; i < sz(segs); i++) {

        for (int j = 0; j < sz(evs[i]); j++) {
            if (j % 2 == 0) cntt[i] += evs[i][j];
            else cntt[i] -= evs[i][j];
        }
        if (sz(evs[i]) & 1) cntt[i]++;
        if (segs[i].ff < m) {
            segss[segs[i].ff].pb({segs[i].sc, cntt[i]});
        }
    }
    for (int i = 0; i < q; i++) {
        int l, r; cin >> l >> r;
        l--; r--;
        qrs[i] = {l, r};
        reqs[l].pb({r, i});
    }
    vector<int> ans(q, 0);
    fenwick fw(m + 2);
    for (int i = 0; i < m; i++) {
        for (auto &u : segss[i]) {
            fw.upd(u.ff + 1, u.sc);
        }
        for (auto &u : reqs[i]) {
            ans[u.sc] = n - (fw.sum(m) - fw.sum(u.ff));
        }
    }
    for (int i = 0; i < q; i++) {
        cout << ans[i] - h[getlca(1, 0, m, qrs[i].ff, qrs[i].sc + 1, getlca)] << '\n';
    }
}

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 7 / 7
• Subtask 4: 18 / 18
• Subtask 5: 24 / 24
• Subtask 6: 41 / 41