제출 #494908

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
494908		Ronin13	Birthday gift (IZhO18_treearray)	C++14	100 / 100	1406 ms	77728 KiB

treearray

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
#define inf 1e9+1
#define linf 1e18+1
using namespace std;
const int NMAX=2e5+1;
void dfs(int v,int e=-1);
vector<vector<int> >g(NMAX);
vector<int>dp(NMAX,0);
int p[NMAX][20];
void dfs(int v,int e){
    p[v][0]=e;
    for(int to:g[v]){
        if(to!=e)dp[to]=dp[v]+1,dfs(to,v);
    }
}
int n;
void prepare(){
    dfs(1);
    for(int i=1;i<=19;i++){
        for(int j=1;j<=n;j++)p[j][i]=-1;
    }
    for(int j=1;j<20;j++){
        for(int i=1;i<=n;i++){
            if(p[i][j-1]!=-1)p[i][j]=p[p[i][j-1]][j-1];
        }
    }
}

int binary_lift(int v,int k){
    for(int j=0;j<20;j++){
        if(k&(1<<j))v=p[v][j];
        if(v==-1)break;
    }
    return v;
}

int lca(int v,int u){
    if(dp[v]>dp[u])swap(u,v);
    int x=dp[u]-dp[v];
    u=binary_lift(u,x);
    if(u==v)return v;
    for(int j=19;j>=0;j--){
        if(p[u][j]!=p[v][j]){
            v=p[v][j];
            u=p[u][j];
        }
    }
    return p[u][0];
}
int a[NMAX];
void solve(){
    cin>>n;
    int m;cin>>m;
    int q;cin>>q;
    for(int i=1;i<n;i++){
        int u,v;cin>>u>>v;
        g[u].pb(v);g[v].pb(u);
    }
    for(int i=1;i<=m;i++)cin>>a[i];
    set<int>st[n+1],st1[n+1];
    prepare();

    for(int i=1;i<m;i++){
        int x=lca(a[i+1],a[i]);
        st[x].insert(i);
    }
    for(int i=1;i<=m;i++){
        st1[a[i]].insert(i);
    }
    while(q--){
        int ind;cin>>ind;
        if(ind==1){
            int pos;cin>>pos;
            int val;cin>>val;
            if(pos>1){
                int x=lca(a[pos],a[pos-1]);
                st[x].erase(pos-1);
            }
            if(pos<m){
                int x=lca(a[pos],a[pos+1]);
                st[x].erase(pos);
            }
            st1[a[pos]].erase(pos);
            a[pos]=val;
            if(pos>1){
                int x=lca(a[pos],a[pos-1]);
                st[x].insert(pos-1);
            }
            if(pos<m){
                int x=lca(a[pos],a[pos+1]);
                st[x].insert(pos);
            }
            st1[val].insert(pos);
        }
        else{
            int l,r,v;cin>>l>>r>>v;
            if(st[v].lower_bound(l)!=st[v].lower_bound(r)){
                int x=*st[v].lower_bound(l);
                cout<<x<<' '<<x+1<<"\n";
                continue;
            }
            if(st1[v].lower_bound(l)!=st1[v].upper_bound(r)){
                int x=*st1[v].lower_bound(l);
                cout<<x<<' '<<x<<"\n";
                continue;
            }
            cout<<-1<<' '<<-1<<"\n";
        }
    }
}

int main(){
   // ios_base::sync_with_stdio(false);cin.tie(0);
    int test=1;//cin>>test;
    while(test--)solve();
}
/*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*/

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