Submission #494905

#	Time	Username	Problem	Language	Result	Execution time	Memory
494905		Ronin13	Birthday gift (IZhO18_treearray)	C++14	0 / 100	4 ms	5884 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;
vector<vector<int> >g(NMAX);
vector<int>a(NMAX);
int p[NMAX][21];
int t_in[NMAX],t_out[NMAX];
bool ispar(int a,int b){
    if(t_in[a]<t_in[b]){
        if(t_out[a]>t_out[b])return true;
    }
    return false;
}
int timer=0;
void dfs(int v,int e=-1){
    p[v][0]=e;
    t_in[v]=timer++;
    for(int to:g[v]){
        if(to==e)continue;
        dfs(to,v);
    }
    t_out[v]=timer++;
}
int n;
void prepare(){
    dfs(1);
    for(int j=1;j<=n;j++){
        for(int i=20;i>=1;i--)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 lca(int a,int b){
    if(ispar(a,b))return a;
    if(ispar(b,a))return b;
    for(int j=20;j>=0;j--){
        int v=p[a][j];
        if(v==-1)continue;
        if(!ispar(v,b))a=v;
    }
    return p[a][0];
}

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<n;i++){
        int x=lca(a[i+1],a[i]);
        st[x].insert(i);
    }
    for(int i=1;i<=n;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<n){
                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<n){
                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: 0 / 12
• Subtask 2: 0 / 18
• Subtask 3: 0 / 26
• Subtask 4: 0 / 44