Submission #863992

#	Time	Username	Problem	Language	Result	Execution time	Memory
863992		Dec0Dedd	Birthday gift (IZhO18_treearray)	C++14	100 / 100	1219 ms	76880 KiB

treearray

#include <bits/stdc++.h>

using namespace std;

const int N = 2e5+10;
const int K = 20;

vector<int> G[N];

int up[K][N], a[N], n, m, q, tin[N], tout[N], t;

void dfs(int v, int p) {
    up[0][v]=p; tin[v]=++t;
    for (int i=1; i<K; ++i) up[i][v]=up[i-1][up[i-1][v]];

    for (auto u : G[v]) {
        if (u == p) continue;
        dfs(u, v);
    } tout[v]=t;
}

bool anc(int v, int u) {
    return tin[v] <= tin[u] && tout[u] <= tout[v];
}

int lca(int v, int u) {
    if (anc(v, u)) return v;
    if (anc(u, v)) return u;

    for (int i=K-1; i>=0; --i) {
        if (!anc(up[i][v], u)) v=up[i][v];
    } return up[0][v];
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    
    cin>>n>>m>>q;

    for (int i=1; i<n; ++i) {
        int a, b; cin>>a>>b;
        G[a].push_back(b);
        G[b].push_back(a);
    } dfs(1, 1);

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

    set<int> st[n+1], ps[n+1];
    for (int i=1; i+1<=m; ++i) {
        st[lca(a[i], a[i+1])].insert(i);
        ps[a[i]].insert(i);
    } ps[a[n]].insert(n);

    while (q--) {
        int tp; cin>>tp;

        if (tp == 1) {
            int p, v; cin>>p>>v;

            ps[a[p]].erase(p);
            ps[v].insert(p);

            if (m == 1) continue;

            if (p == 1) {
                st[lca(a[p], a[p+1])].erase(p);
                a[p]=v;
                st[lca(a[p], a[p+1])].insert(p);
            } else if (p == m) {
                st[lca(a[p-1], a[p])].erase(p-1);
                a[p]=v;
                st[lca(a[p-1], a[p])].insert(p-1);
            } else {
                st[lca(a[p], a[p+1])].erase(p);
                st[lca(a[p-1], a[p])].erase(p-1);
                a[p]=v;
                st[lca(a[p], a[p+1])].insert(p);
                st[lca(a[p-1], a[p])].insert(p-1);
            }
        } else {
            int l, r, v; cin>>l>>r>>v;

            auto ptr=ps[v].lower_bound(l);
            if (ptr != ps[v].end() && *ptr <= r) {
                cout<<(*ptr)<<" "<<(*ptr)<<"\n";
                continue;
            }

            if (st[v].empty()) cout<<-1<<" "<<-1<<"\n";
            else {
                auto ptr=st[v].lower_bound(l);
                if (ptr == st[v].end()) cout<<-1<<" "<<-1<<"\n";
                else if (*ptr < r) cout<<(*ptr)<<" "<<(*ptr)+1<<"\n";
                else cout<<-1<<" "<<-1<<"\n";
            }
        }
    }
}

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