Submission #1250727

#	Time	Username	Problem	Language	Result	Execution time	Memory
1250727		dhuyyyy	Birthday gift (IZhO18_treearray)	C++20	100 / 100	473 ms	57012 KiB

treearray

#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;

using ll = long long;
using ii = pair<int, int>;
using pii = pair<int,ii>;
using aa = array<int,3>;

const int N = 2e5+5;

multiset<ii> ms[N];
int n,m,q,type,u,v,l,r,pos,cnt = 0;
int depth[N],chain[N],par[N],a[N],sub[N];
vector <int> adj[N];
void subtree(int u,int p){
    sub[u] = 1;
    par[u] = p;
    depth[u] = depth[p] + 1;
    for (int v : adj[u]){
        if (v == p) continue;
        subtree(v,u);
        sub[u] += sub[v];
    }
}
void dfs(int u,int p){
    int heavy = 0;
    for (int v : adj[u]){
        if (v == p) continue;
        if (sub[v] > sub[heavy]) heavy = v;
    }
    if (!heavy) return;
    chain[heavy] = chain[u];
    dfs(heavy,u);
    for (int v : adj[u]){
        if (v != p && v != heavy){
            chain[v] = v;
            dfs(v,u);
        }
    }
}
int lca(int u,int v){
    while (chain[u] != chain[v]){
        if (depth[chain[u]] < depth[chain[v]]) swap(u,v);
        u = par[chain[u]];
    }
    return (depth[u] < depth[v] ? u : v);
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    cin >> n >> m >> q;
    for (int i = 1; i < n; i++){
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    cnt = 0;
    subtree(1,0);
    dfs(1,0);
    for (int i = 1; i <= m; i++){
        cin >> a[i];
        if (i != 1) ms[lca(a[i-1],a[i])].insert({i-1,i});
        ms[a[i]].insert({i,i});
    }
    while (q--){
        cin >> type;
        if (type == 1){
            cin >> pos >> v;
            if (a[pos] == v) continue;
            if (pos != m){
                 ms[lca(a[pos],a[pos+1])].erase({pos,pos+1});
                 ms[lca(v,a[pos+1])].insert({pos,pos+1});
            }
            if (pos != 1){
                 ms[lca(a[pos-1],a[pos])].erase({pos-1,pos});
                 ms[lca(a[pos-1],v)].insert({pos-1,pos});
            }
            ms[a[pos]].erase({pos,pos});
            ms[v].insert({pos,pos});
            a[pos] = v;
        } else{
            cin >> l >> r >> v;
            auto tmp = ms[v].lower_bound({l,-1});
            if (tmp == ms[v].end()) {
                cout << -1 << ' ' << -1 << '\n';
                continue;
            }
            ii ans = *tmp;
            bool ok = ans.se > r;
            cout << (!ok ? ans.fi : -1) << ' ' << (!ok ? ans.se : -1) << '\n';
        }
    }
    return 0;
}

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