Submission #1163982

#	Time	Username	Problem	Language	Result	Execution time	Memory
1163982		SulA	Birthday gift (IZhO18_treearray)	C++20	100 / 100	594 ms	78808 KiB

treearray

#include <bits/stdc++.h>
#define all(a) a.begin(), a.end()
#define popcount __builtin_popcountll
using namespace std;

set<int> ind[200000], ind2[200000];
vector<int> adj[200000];
int in[200000], out[200000], par[200000][18], t = 0, n, m;
int a[200000];

void dfs(int u = 0, int p = -1) {
    in[u] = t++;
    for (int v : adj[u]) if (v != p) {
            par[v][0] = u;
            for (int i = 1; i < 18; i++)
                par[v][i] = par[par[v][i-1]][i-1];
            dfs(v, u);
        }
    out[u] = t++;
}

bool is_anc(int u, int v) {
    return in[u] <= in[v] && out[v] <= out[u];
}

int lca(int u, int v) {
    if (is_anc(u, v)) return u;
    if (is_anc(v, u)) return v;
    for (int i = 17; i >= 0; i--) if (!is_anc(par[v][i], u))
            v = par[v][i];
    return par[v][0];
}

void update(int i, int x) {
    ind[a[i]].erase(i);
    int L;
    if (i != 0) {
        L = lca(a[i-1], a[i]);
        ind2[L].erase(i-1);
    }
    if (i != m-1) {
        L = lca(a[i], a[i+1]);
        ind2[L].erase(i);
    }
    a[i] = x;
    ind[a[i]].insert(i);
    if (i != 0) {
        L = lca(a[i-1], a[i]);
        ind2[L].insert(i-1);
    }
    if (i != m-1) {
        L = lca(a[i], a[i+1]);
        ind2[L].insert(i);
    }
}

pair<int,int> solve(int l, int r, int u) {
    auto it = ind[u].lower_bound(l);
    if (it != ind[u].end() && *it <= r)
        return {*it, *it};
    it = ind2[u].lower_bound(l);
    if (it != ind2[u].end() && *it + 1 <= r)
        return {*it, *it + 1};
    return {-2, -2};
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int q; cin>>n>>m>>q;
    for (int i = 0; i < n-1; i++) {
        int u,v; cin>>u>>v;
        adj[--u].push_back(--v);
        adj[v].push_back(u);
    }
    dfs();
    for (int i = 0; i < m; i++) {
        cin>>a[i];
        a[i]--;
        ind[a[i]].insert(i);
    }
    for (int i = 0; i < m-1; i++)
        ind2[lca(a[i], a[i+1])].insert(i);
    while (q--) {
        cin>>t;
        if (t == 1) {
            int i,x; cin>>i>>x;
            update(--i, --x);
//            for (i = 0; i < n; i++) {
//                for (int x : ind[i]) cout<<x<<' ';
//                cout<<'\n';
//            }
        } else {
            int l,r,u; cin>>l>>r>>u;
            auto [x, y] = solve(--l, --r, --u);
            cout << 1+x << " " << 1+y << "\n";
        }
    }
}

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