제출 #651307

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
651307		Astrayt	Birthday gift (IZhO18_treearray)	C++17	12 / 100	16 ms	24100 KiB

treearray

//君の手を握ってしまったら
//孤独を知らないこの街には
//もう二度と帰ってくることはできないのでしょう
//君が手を差し伸べた 光で影が生まれる
//歌って聞かせて この話の続き
//連れて行って見たことない星まで
//さユリ - 花の塔
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
#define starburst ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define pii pair<int,int>
#define pb push_back
#define ff first
#define ss second
#define maxn 200005

int a[maxn], dep[maxn], anc[21][maxn];
vector<int> adj[maxn];
set<int> pos[maxn], pos2[maxn];

void dfs(int u, int p, int d){
    dep[u] = d;
    for(int v:adj[u]){
        if(v == p) continue;
        anc[0][v] = u;
        dfs(v, u, d + 1);
    }
}

int lca(int u, int v){
    if(dep[v] > dep[u]) swap(u, v);
    for(int i = 20; i >= 0; --i){
        if(dep[anc[i][u]] >= dep[v]) u = anc[i][u];
    }
    if(u == v) return u;
    for(int i = 20; i >= 0; --i){
        if(anc[i][u] != anc[i][v]) u = anc[i][u], v = anc[i][v];
    }
    return anc[0][u];
}

void solve(){
    int n, m, q; cin >> n >> m >> q;
    for(int i = 1; i < n; ++i){
        int u, v; cin >> u >> v;
        adj[u].pb(v); adj[v].pb(u);
    }
    for(int i = 0; i <= 20; ++i) anc[i][1] = 1;
    dfs(1, 0, 0);
    for(int i = 1; i <= 20; ++i){
        for(int v = 2; v <= n; ++v){
            anc[i][v] = anc[i - 1][anc[i - 1][v]];
        }
    }
    for(int i = 1; i <= m; ++i) cin >> a[i], pos2[a[i]].insert(i);
    for(int i = 1; i < m; ++i){
        pos[lca(a[i], a[i + 1])].insert(i);
    }
    for(int i = 1; i <= q; ++i){
        int t, l, r; cin >> t >> l >> r;
        if(t == 1){
            pos2[a[l]].erase(l);
            pos2[r].insert(l);
            if(l != n){
                int u = lca(a[l], a[l + 1]);
                pos[u].erase(l);
                u = lca(r, a[l + 1]);
                pos[u].insert(l);
            }
            if(i != 1){
                int u = lca(a[l], a[l - 1]);
                pos[u].erase(l - 1);
                u = lca(r, a[l - 1]);
                pos[u].insert(l - 1);
            }
            a[l] = r;
        }else{
            int v; cin >> v;
            auto x = pos2[v].lower_bound(l);
            if(x != pos2[v].end() && *x <= r) {
                cout << *x << ' ' << *x << '\n';
                continue;
            }
            x = pos[v].lower_bound(l);
            if(x != pos[v].end() && *x < r){
                cout << *x << ' ' << (*x) + 1 << '\n';
            }else cout << "-1 -1\n";
        }
    }
}

signed main(){
    starburst
    int t = 1; //cin >> t;
    while(t--) solve();
}

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