Submission #428506

#	Time	Username	Problem	Language	Result	Execution time	Memory
428506		jovan_b	Birthday gift (IZhO18_treearray)	C++17	100 / 100	1528 ms	84016 KiB

treearray

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;

const int MAXN = 200000;
const int MXLOG = 18;

int par[MAXN+5][MXLOG+1];
vector <int> graf[MAXN+5];
int in[MAXN+5];
int out[MAXN+5];

int tjm;
void dfs(int v, int p){
    par[v][0] = p;
    in[v] = ++tjm;
    for(int j=1; j<=MXLOG; j++) par[v][j] = par[par[v][j-1]][j-1];
    for(auto c : graf[v]) if(c != p) dfs(c, v);
    out[v] = tjm;
}

int val[MAXN+5];

bool is_parent(int a, int b){
    return (a == 0) || (in[a] <= in[b] && out[b] <= out[a]);
}

int lca(int a, int b){
    if(is_parent(a, b)) return a;
    for(int j=MXLOG; j>=0; j--){
        if(!is_parent(par[a][j], b)) a = par[a][j];
    }
    return par[a][0];
}

set <int> p1[MAXN+5];
set <int> p2[MAXN+5];

int main(){
    ios_base::sync_with_stdio(false), cin.tie(0);
	cout.precision(10);
	cout << fixed;

    int n, m, q;
    cin >> n >> m >> q;
    for(int i=1; i<n; i++){
        int a, b;
        cin >> a >> b;
        graf[a].push_back(b);
        graf[b].push_back(a);
    }
    dfs(1, 0);
    for(int i=1; i<=m; i++){
        cin >> val[i];
        p1[val[i]].insert(i);
    }
    for(int i=2; i<=m; i++){
        p2[lca(val[i-1], val[i])].insert(i);
    }
    while(q--){
        int tp;
        cin >> tp;
        if(tp == 1){
            int pos, v;
            cin >> pos >> v;
            p1[val[pos]].erase(pos);
            if(pos > 1) p2[lca(val[pos], val[pos-1])].erase(pos);
            if(pos < m) p2[lca(val[pos], val[pos+1])].erase(pos+1);
            val[pos] = v;
            p1[val[pos]].insert(pos);
            if(pos > 1) p2[lca(val[pos], val[pos-1])].insert(pos);
            if(pos < m) p2[lca(val[pos], val[pos+1])].insert(pos+1);
        }
        else{
            int l, r, v;
            cin >> l >> r >> v;
            auto x = p1[v].lower_bound(l);
            if(x != p1[v].end() && *x <= r){
                cout << *x << " " << *x << "\n";
                continue;
            }
            x = p2[v].lower_bound(l+1);
            if(x != p2[v].end() && *x <= r){
                cout << (*x)-1 << " " << *x << "\n";
                continue;
            }
            cout << "-1 -1\n";
        }
    }
    return 0;
}

/*
5 4 4
1 2
3 1
3 4
5 3
4 5 2 3
2 1 3 1
1 3 5
2 3 4 5
2 1 3 1
*/

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