Submission #824700

#	Time	Username	Problem	Language	Result	Execution time	Memory
824700		dimashhh	Birthday gift (IZhO18_treearray)	C++17	0 / 100	14 ms	23852 KiB

treearray

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N = 2e5 + 1,MOD = 998244353;

int n,m,q,a[N],up[N][20],tin[N],tout[N],timer = 0,b[N];
vector<int> g[N];
set<int> t[N],f[N];
int ans;
void dfs(int v,int pr = 1){
    tin[v] = ++timer;
    up[v][0] = pr;
    for(int i = 1;i <= 18;i++){
        up[v][i] = up[up[v][i - 1]][i - 1];
    }
    for(int to:g[v]){
        if(to != pr) dfs(to,v);
    }
    tout[v] = timer;
}
bool is(int v,int u){
    return (tin[v] <= tin[u] && tout[v] >= tout[u]);
}
int lca(int v,int u){
    if(is(v,u)) return v;
    if(is(u,v)) return u;
    for(int i = 18;i >= 0;i--){
        if(!is(up[v][i],u)){
            v = up[v][i];
        }
    }
    return up[v][0];
}
void test(){
    cin >> n >> m >> q;
    for(int i = 1;i <= n - 1;i++){
        int x,y;
        cin >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    dfs(1);
    for(int i = 1;i <= m;i++){
        cin >> a[i];
        t[a[i]].insert(i);
        if(i > 1) b[i - 1] = lca(a[i - 1],a[i]);
        f[b[i - 1]].insert(i - 1);
    }
    while(q--){
        int tp;
        cin >> tp;
        if(tp == 1){
            int pos,v;
            cin >> pos >> v;
            t[a[pos]].erase(pos);
            if(pos < m){
                int x = lca(v,a[pos + 1]);
                f[b[pos]].erase(pos);
                b[pos] = x;
                f[b[pos]].insert(pos);
            }
            if(pos > 1){
                int x = lca(a[pos - 1],v);
                f[b[pos - 1]].erase(pos - 1);                
                b[pos - 1] = x;
                f[b[pos - 1]].insert(pos - 1);                
            }
            a[pos] = v;
            t[a[pos]].insert(pos);
        }else{
            int l,r,v;
            cin >> l >> r >> v;
            if(l == r){
                if(v == a[l]){
                    cout << l << ' ' << r << '\n';
                }else{
                    cout << -1 << ' ' << -1 << '\n';
                }
                continue;
            }
            auto it = f[v].lower_bound(l);
            if(it != f[v].end() && *it <= r){
                cout << *it << ' ' << *it + 1 << '\n'; 
            }else{
                auto it = t[v].lower_bound(l);
                if(it != t[v].end() && *it <= r){
                    cout << *it << ' ' << *it << '\n';
                    continue;
                }
                cout << -1 << ' ' << -1 << '\n';
            }
        }
    }
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int t = 1;
    //cin >> t;
    while(t--) test();
}

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