Submission #767732

#	Time	Username	Problem	Language	Result	Execution time	Memory
767732		PurpleCrayon	Tourism (JOI23_tourism)	C++17	100 / 100	668 ms	61844 KiB

tourism

#include <bits/stdc++.h>
using namespace std;
 
#define sz(v) int(v.size())
#define ar array
typedef long long ll;
const int N = 1e5+10, MOD = 1e9+7;
const int L = 19;

struct FT {
    vector<int> bit;
    FT(int n): bit(n) {}

    void upd(int i, int x) {
        for (; i < sz(bit); i |= i+1) bit[i] += x;
    }

    int qry(int i) {
        int ans = 0;
        for (++i; i > 0; i &= i-1) ans += bit[i-1];
        return ans;
    }
};

int n, m, q, st[N], en[N], depth[N], tt = 0;
vector<int> adj[N];

vector<int> lca_et;
int sparse[2 * N][L], st_lca[N], en_lca[N];

int dep_min(int a, int b) {
    return depth[a] < depth[b] ? a : b;
}

void build_rmq() {
    int k = sz(lca_et);
    for (int i = 0; i < k; i++) sparse[i][0] = lca_et[i];
    for (int c = 2, l = 1; c <= k; c *= 2, l++) {
        for (int i = 0; i + c <= k; i++) {
            sparse[i][l] = dep_min(sparse[i][l-1], sparse[i + c/2][l-1]);
        }
    }
}

int rmq_qry(int l, int r) {
    int lg = 31 - __builtin_clz(r - l + 1);
    int len = 1 << lg;
    return dep_min(sparse[l][lg], sparse[r - len + 1][lg]);
}

int lca(int a, int b) {
    if (st_lca[a] > st_lca[b]) swap(a, b);
    return rmq_qry(st_lca[a], en_lca[b]);
}

void dfs(int c, int p) {
    if (p != -1) depth[c] = depth[p] + 1;
    st[c] = tt++;

    st_lca[c] = en_lca[c] = sz(lca_et);
    lca_et.push_back(c);
    for (int nxt : adj[c]) if (nxt != p) {
        dfs(nxt, c);

        en_lca[c] = sz(lca_et);
        lca_et.push_back(c);
    }

    en[c] = tt-1;
}

int ans[N], c[N], lca_l[N], lca_r[N];
int rev[N], par[N], w[N];
pair<int, int> range[N];
vector<int> aux[N];
vector<pair<int, int>> ev[N];

void dfs_aux_range(int c) {
    for (int nxt : aux[c]) {
        dfs_aux_range(nxt);
        range[c].first = max(range[c].first, range[nxt].first);
        range[c].second = min(range[c].second, range[nxt].second);
    }
}

void rec(int l, int r, vector<ar<int, 3>> qs) {
    if (!sz(qs)) return;
    if (r <= l) return;

    int m = (l + r) / 2; // [l..m], [m+1..r]
    vector<ar<int, 3>> one, two, mine;
    for (auto qi : qs) {
        if (qi[1] <= m)
            one.push_back(qi);
        else if (qi[0] > m)
            two.push_back(qi);
        else
            mine.push_back(qi);
    }

    rec(l, m, one), rec(m+1, r, two);

    vector<int> use;
    for (int i = l; i <= r; i++) use.push_back(c[i]);

    sort(use.begin(), use.end(), [&](int x, int y) {
        return st[x] < st[y];
    });

    use.resize(unique(use.begin(), use.end()) - use.begin());
    int base = sz(use);
    for (int i = 0; i < base; i++) {
        use.push_back(lca(use[i], use[(i+1) % base]));
    }

    sort(use.begin(), use.end(), [&](int x, int y) {
        return st[x] < st[y];
    });

    use.resize(unique(use.begin(), use.end()) - use.begin());
    for (int i = 0; i < sz(use); i++) {
        rev[use[i]] = i;
        aux[i].clear();
    }

    for (int i = 1; i < sz(use); i++) {
        par[i] = rev[lca(use[i-1], use[i])];
        aux[par[i]].push_back(i);
        w[i] = depth[use[i]] - depth[use[par[i]]];
    }
    
    int k = sz(use);
    // max index of something on the left, min index of something on the right
    for (int i = 0; i < k; i++) {
        range[i] = {-1, MOD};
    }

    for (int i = l; i <= m; i++) {
        int cur = rev[c[i]];
        range[cur].first = max(range[cur].first, i);
    }

    for (int i = m+1; i <= r; i++) {
        int cur = rev[c[i]];
        range[cur].second = min(range[cur].second, i);
    }

    dfs_aux_range(0);
    for (int i = m; i >= l; i--) {
        lca_l[i] = c[i];
        if (i < m) lca_l[i] = lca(lca_l[i], lca_l[i+1]);
    }

    for (int i = m+1; i <= r; i++) {
        lca_r[i] = c[i];
        if (i > m+1) lca_r[i] = lca(lca_r[i], lca_r[i-1]);
    }

    int sum = 0;
    for (int j = 1; j < k; j++) sum += w[j];
    int top = use[0];

    for (int i = l; i <= r; i++) ev[i].clear();

    FT bit(r - l + 1);
    auto add = [&](int L, int R, int x) {
        if (R < L) return;
        L -= l;
        R -= l;
        bit.upd(L, +x);
        bit.upd(R+1, -x);
    };

    auto qry = [&](int i) {
        return bit.qry(i - l);
    };

    for (int j = 1; j < k; j++) {
        if (range[j].first < l) {
            ev[l].push_back({range[j].second, -w[j]});
        }
    }

    for (auto [L, R, i] : mine) {
        ans[i] += sum;
        ans[i] -= depth[lca(lca_l[L], lca_r[R])] - depth[top];

        ev[L].push_back({R, i});

        /*
        for (int j = 1; j < k; j++) {
            if (range[j].first < L && R < range[j].second) {
                ans[i] -= w[j];
            }
        }
        */
    }

    for (int j = 1; j < k; j++) {
        if (range[j].first >= l) {
            ev[range[j].first].push_back({range[j].second, -w[j]});
        }
    }

    for (int i = l; i <= r; i++) {
        for (auto [R, x] : ev[i]) {
            if (x >= 0) {
                ans[x] += qry(R);
            } else {
                x *= -1;
                add(l, min(r, R-1), -x);
            }
        }
    }
}

void solve() {
    cin >> n >> m >> q;
    for (int i = 0; i < n-1; i++) {
        int a, b; cin >> a >> b, --a, --b;
        adj[a].push_back(b), adj[b].push_back(a);
    }

    dfs(0, -1);
    build_rmq();

    for (int i = 0; i < m; i++) {
        cin >> c[i], --c[i];
    }

    vector<ar<int, 3>> qs(q);
    for (int i = 0; i < q; i++) {
        int l, r; cin >> l >> r, --l, --r;
        qs[i] = {l, r, i};
    }

    rec(0, m-1, qs);

    for (int i = 0; i < q; i++) cout << ans[i]+1 << '\n';
}
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int T = 1;
    // cin >> T;
    while (T--) solve();
}

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