Submission #1265529

#	Time	Username	Problem	Language	Result	Execution time	Memory
1265529		rayan_bd	Birthday gift (IZhO18_treearray)	C++20	100 / 100	456 ms	81276 KiB

treearray

#include <bits/stdc++.h>
using namespace std;

const int mxN = 2e5 + 10;
const int mxB = 26;

vector<int> adj[mxN];
set<int> lca_st[mxN], pos_st[mxN];
int dp[mxN][mxB], depth[mxN], a[mxN];

void dfs(int u = 1, int par = 0){
    depth[u] = depth[par] + 1;
    dp[u][0] = par;
    for(int i = 1; i < mxB; ++i) dp[u][i] = dp[dp[u][i - 1]][i - 1];
    for(auto it : adj[u]){
        if(it ^ par){
            dfs(it, u);
        }
    }
}

int kth(int u, int k){
    for(int i = 0; i < mxB; ++i){
        if(k & (1 << i)) u = dp[u][i];
    }
    return u;
}

int lca(int u, int v){
    if(depth[u] < depth[v]) swap(u, v);
    u = kth(u, depth[u] - depth[v]);
    if(u == v) return u;
    for(int i = mxB - 1; i >= 0; --i){
        if(dp[u][i] ^ dp[v][i]){
            u = dp[u][i];
            v = dp[v][i];
        }
    }
    return dp[u][0];
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr); cout.tie(nullptr);

    int n, m, q, u, v, l, r, idx, t;
    cin >> n >> m >> q;

    for(int i = 0; i < n - 1; ++i){
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    dfs();

    for(int i = 0; i < m; ++i) cin >> a[i];

    for(int i = 0; i < m; ++i){
        if(i + 1 < m) lca_st[lca(a[i], a[i + 1])].insert(i);
        pos_st[a[i]].insert(i);
    }

    auto add = [&](int idx, int v){
        pos_st[a[idx]].erase(idx);
        pos_st[v].insert(idx);
        if(idx + 1 < m){
            lca_st[lca(a[idx], a[idx + 1])].erase(idx);
            lca_st[lca(v, a[idx + 1])].insert(idx);
        }
        if(idx - 1 >= 0){
            lca_st[lca(a[idx], a[idx - 1])].erase(idx - 1);
            lca_st[lca(v, a[idx - 1])].insert(idx - 1);
        }
        a[idx] = v;
    };

    auto answer = [&](int l, int r, int v){
        auto lb = pos_st[v].lower_bound(l - 1);
        if(lb != pos_st[v].end() && (*lb + 1) >= l && (*lb + 1) <= r){
            cout << *lb + 1 << " " << *lb + 1 << "\n";
        }else{
            lb = lca_st[v].lower_bound(l - 1);
            if(lb != lca_st[v].end() && (*lb + 2) <= r){
                cout << *lb + 1 << " " << *lb + 2 << "\n";
            }else{
                cout << "-1 -1\n";
            }
        }
    };

    for(int i = 0; i < q; ++i){
        cin >> t;
        if(t == 1){
            cin >> idx >> v; --idx;
            add(idx, v);
        }else{
            cin >> l >> r >> v;
            answer(l, r, v);
        }
    }

    return 0;
}

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