제출 #1164847

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1164847		AlgorithmWarrior	Birthday gift (IZhO18_treearray)	C++20	100 / 100	872 ms	80364 KiB

treearray

#include <bits/stdc++.h>

using namespace std;

int const MAX=2e5+5;
int const LOG=20;
int n,m,q;
vector<int>tree[MAX];
int v1[MAX],v2[MAX];
int lift[MAX][LOG];
set<int>pos1[MAX],pos2[MAX];
int h[MAX];

void read(){
    cin>>n>>m>>q;
    int i;
    for(i=1;i<n;++i){
        int u,v;
        cin>>u>>v;
        tree[u].push_back(v);
        tree[v].push_back(u);
    }
    for(i=1;i<=m;++i)
        cin>>v1[i];
}

void dfs(int nod){
    for(auto fiu : tree[nod])
        if(fiu!=lift[nod][0]){
            lift[fiu][0]=nod;
            h[fiu]=h[nod]+1;
            dfs(fiu);
        }
}

int lca(int nod1,int nod2){
    if(h[nod1]<h[nod2])
        swap(nod1,nod2);
    int dif=h[nod1]-h[nod2];
    int i;
    for(i=0;i<LOG;++i)
        if((1<<i)&dif)
            nod1=lift[nod1][i];
    if(nod1==nod2)
        return nod1;
    for(i=LOG-1;i>=0;--i)
        if(lift[nod1][i]!=lift[nod2][i]){
            nod1=lift[nod1][i];
            nod2=lift[nod2][i];
        }
    return lift[nod1][0];
}

void precalc(){
    int i,j;
    for(j=1;j<LOG;++j)
        for(i=1;i<=n;++i)
            lift[i][j]=lift[lift[i][j-1]][j-1];
    for(i=1;i<m;++i)
        v2[i]=lca(v1[i],v1[i+1]);
    for(i=1;i<=m;++i)
        pos1[v1[i]].insert(i);
    for(i=1;i<m;++i)
        pos2[v2[i]].insert(i);
}

void update(int pos,int val){
    pos1[v1[pos]].erase(pos);
    if(pos>1)
        pos2[v2[pos-1]].erase(pos-1);
    if(pos<m)
        pos2[v2[pos]].erase(pos);
    v1[pos]=val;
    pos1[val].insert(pos);
    if(pos>1){
        v2[pos-1]=lca(v1[pos-1],v1[pos]);
        pos2[v2[pos-1]].insert(pos-1);
    }
    if(pos<m){
        v2[pos]=lca(v1[pos],v1[pos+1]);
        pos2[v2[pos]].insert(pos);
    }
}

void query(int l,int r,int val){
    auto it=pos1[val].lower_bound(l);
    if(it!=pos1[val].end() && *it<=r){
        cout<<*it<<' '<<*it<<'\n';
        return;
    }
    it=pos2[val].lower_bound(l);
    if(it!=pos2[val].end() && *it<r){
        cout<<*it<<' '<<*it+1<<'\n';
        return;
    }
    cout<<"-1 -1\n";
}

void process_queries(){
    int i;
    for(i=1;i<=q;++i){
        int type;
        cin>>type;
        if(type==1){
            int pos,val;
            cin>>pos>>val;
            update(pos,val);
        }
        else{
            int l,r,val;
            cin>>l>>r>>val;
            query(l,r,val);
        }
    }
}

int main()
{
    read();
    dfs(1);
    precalc();
    process_queries();
    return 0;
}

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