제출 #1265528

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1265528		rayan_bd	Birthday gift (IZhO18_treearray)	C++20	100 / 100	456 ms	82804 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], st[mxN], en[mxN], timer = -1;
void dfs(int u = 1, int par = 0){
    st[u] = ++timer;
    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);
        }
    }
    en[u] = ++timer;
}
bool in_subtree(int u, int v){
    return st[v] >= st[u] && en[v] <= en[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;
    memset(dp, 0, sizeof(dp));
    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 - 1; ++i){
        lca_st[lca(a[i], a[i + 1])].insert(i);
        pos_st[a[i]].insert(i);
       // cout << lca(a[i], a[i + 1]) << " " << a[i] << " " << a[i + 1] << endl;
    }
    pos_st[a[m - 1]].insert(m - 1);
    for(int i = 0; i < q; ++i){
        cin >> t;
        if(t == 1){
            cin >> idx >> v; --idx;
            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;
        }else{
            cin >> l >> r >> 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";
                }
            }
        }
    }
    return 0;
}

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