Submission #1156848

#	Time	Username	Problem	Language	Result	Execution time	Memory
1156848		andrewp	Birthday gift (IZhO18_treearray)	C++20	56 / 100	668 ms	65504 KiB

treearray

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define pii pair<int,int>
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
const int N=2e5+10;

int n, m, q, up[N][12], a[N], dep[N];
vector<int> g[N];
set<int> st1[N], st2[N];

void dfs(int x, int par) {
    up[x][0]=par;
    dep[x]=dep[par]+1;
    for (int i=1; i<12; i++)
        up[x][i]=up[up[x][i-1]][i-1];
    for (int u:g[x])
        if (u!=par)
            dfs(u, x);
}

int raise(int x, int y) {
    int z=0;
    while (y) {
        if (y&1)
            x=up[x][z];
        z++;
        y>>=1;
    }
    return x;
}

int lca(int a, int b) {
    if (dep[a]>dep[b])
        swap(a, b);
    int x=dep[b]-dep[a];
    b=raise(b, x);
    if (a==b)
        return a;
    for (int i=11; i>=0; i--) {
        if (up[a][i]!=up[b][i]) {
            a=up[a][i];
            b=up[b][i];
        }
    }
    return up[a][0];
}

int32_t main () {
    ios::sync_with_stdio(false), cin.tie(0);

    cin >> n >> m >> q;
    for (int i=1; i<n; i++) {
        int u, v;
        cin >> u >> v;
        g[u].pb(v);
        g[v].pb(u);
    }
    dfs(1, 0);
    for (int i=1; i<=m; i++) {
        cin >> a[i];
        st1[a[i]].insert(i);
    }
    for (int i=1; i<m; i++) {
        st2[lca(a[i], a[i+1])].insert(i);
    }
    while (q--) {
        int tp;
        cin >> tp;
        if (tp==1) {
            int pos, v;
            cin >> pos >> v;
            st1[a[pos]].erase(pos);
            st1[v].insert(pos);
            if (pos>1) {
                st2[lca(a[pos], a[pos-1])].erase(pos-1);
                st2[lca(v, a[pos-1])].insert(pos-1);
            }
            if (pos<m) {
                st2[lca(a[pos], a[pos+1])].erase(pos);
                st2[lca(v, a[pos+1])].insert(pos);
            }
            a[pos]=v;
        }
        else {
            int l, r, v;
            cin >> l >> r >> v;
            auto it=st1[v].lower_bound(l);
            if (it!=st1[v].end()) {
                if (*it<=r) {
                    cout << *it << ' ' << *it << '\n';
                    continue;
                }
            }
            it=st2[v].lower_bound(l);
            if (it!=st2[v].end()) {
                if (*it<r) {
                    cout << *it << ' ' << *it+1 << '\n';
                    continue;
                }
            }
            cout << -1 << ' ' << -1 << '\n';
        }
    }
    return 0;
}

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