제출 #1127713

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1127713		boris_7	Birthday gift (IZhO18_treearray)	C++20	100 / 100	963 ms	85180 KiB

treearray

#include<bits/stdc++.h>

using namespace std;
using ll = long long;

vector<set<int>>len1,len2;
vector<vector<int>>gp,up;
vector<int>tin,tout;
int timer = 0;

void dfs(int u,int p){
    tin[u]=timer++;
    up[u][0]=p;
    for(int i = 1;i<20;i++) up[u][i]=up[up[u][i-1]][i-1];
    for(int &i:gp[u]){
        if(i!=p){
            dfs(i,u);
        }
    }
    tout[u]=timer;
}

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

int lca(int u,int v){
    if(isok(u,v)) return u;
    if(isok(v,u)) return v;
    for(int i = 19;i>=0;i--){
        if(!isok(up[u][i],v)) u = up[u][i];
    }
    return up[u][0];
}

pair<int,int>query1(int l,int r,int x){
    auto a = len1[x].lower_bound(l);
    if(a!=len1[x].end() && (*a)<=r) return {(*a)+1,(*a)+1};
    else return {-1,-1};
}

pair<int,int>query2(int l,int r,int x){
    auto a = len2[x].lower_bound(l);
    if(a!=len2[x].end() && (*a)<=r) return {(*a)+1,(*a)+2};
    else return {-1,-1};
}

void solve(){
    int n,m,q;
    cin>>n>>m>>q;
    tin = tout = vector<int>(n);
    gp = vector<vector<int>>(n);
    up = vector<vector<int>>(n,vector<int>(20));
    for(int i = 1;i<n;i++){
        int u,v;
        cin>>u>>v;
        gp[--u].push_back(--v);
        gp[v].push_back(u);
    }
    dfs(0,0);
    vector<int>a(m);
    for(int &i:a) cin>>i,--i;
    len2 = len1 = vector<set<int>>(n);
    for(int i = 0;i<m;i++){
        len1[a[i]].insert(i);
    }
    for(int i = 0;i+1<m;i++){
        len2[lca(a[i],a[i+1])].insert(i);
    }
    while(q--){
        int type;
        cin>>type;
        if(type==1){
            int pos,x;
            cin>>pos>>x;
            --pos,--x;
            if(pos>0) len2[lca(a[pos-1],a[pos])].erase(pos-1);
            if(pos+1<m) len2[lca(a[pos],a[pos+1])].erase(pos);
            len1[a[pos]].erase(pos);
            a[pos]=x;
            len1[x].insert(pos);
            if(pos>0) len2[lca(a[pos-1],a[pos])].insert(pos-1);
            if(pos+1<m) len2[lca(a[pos],a[pos+1])].insert(pos);
        }
        else{
            int l,r,x;
            cin>>l>>r>>x;
            --l,--r,--x;
            auto ans = query1(l,r,x);
            ans = max(ans,query2(l,r-1,x));
            cout<<ans.first<<" "<<ans.second<<endl;
        }
    }
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr);
    // int t;cin>>t;while(t--)
        solve();
}

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