Submission #440638

#	Time	Username	Problem	Language	Result	Execution time	Memory
440638		leaked	Birthday gift (IZhO18_treearray)	C++17	100 / 100	1202 ms	83152 KiB

treearray

#include <bits/stdc++.h>

#define m_p make_pair
#define vec vector
#define pb push_back
#define sz(x) (int)x.size()
#define pw(x) (1LL<<x)
#define f first
#define s second

using namespace std;
const int N=2e5+1;
const int lg=18;
vec<int> g[N];
int tin[N],tout[N],tt=1,up[N][lg];
set<int>st[N];
set<int>sob[N];
int vs[N];
void dfs(int v,int p){
    tin[v]=tt++;
    up[v][0]=p;
    for(int i=1;i<lg;i++) up[v][i]=up[up[v][i-1]][i-1];
    for(auto &z : g[v]){
        if(z==p) continue;
        dfs(z,v);
    }
    tout[v]=tt-1;
}
bool is(int a,int b){
    return tin[a]<=tin[b]&&tout[a]>=tout[b];
}
int lca(int a,int b){
    if(is(a,b)) return a;
    if(is(b,a)) return b;
    for(int i=lg-1;i>=0;i--){
        if(!is(up[a][i],b)) a=up[a][i];
    }
    return up[a][0];
}
/// [i,i+1]
signed main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int n,m,q;
    cin>>n>>m>>q;
    for(int i=1;i<n;i++){
        int v,u;
        cin>>v>>u;--v;--u;
        g[v].pb(u);g[u].pb(v);
    }
    dfs(0,0);
    for(int i=0;i<m;i++){
        cin>>vs[i];--vs[i];
        sob[vs[i]].insert(i);
        if(i) st[lca(vs[i],vs[i-1])].insert(i-1);
    }
    while(q--){
        int t;
        cin>>t;
        if(t==1){
            int id,v;
            cin>>id>>v;--v;--id;
            if(id) st[lca(vs[id-1],vs[id])].erase(id-1);
            sob[vs[id]].erase(id);
            if(id+1<m) st[lca(vs[id+1],vs[id])].erase(id);
            vs[id]=v;
            if(id) st[lca(vs[id-1],vs[id])].insert(id-1);
            sob[vs[id]].insert(id);
            if(id+1<m) st[lca(vs[id+1],vs[id])].insert(id);
        }
        else{
            int l,r,v;
            cin>>l>>r>>v;
            --l;--r;--v;
            int x=-1,y=-1;
            auto it=sob[v].lower_bound(l);
            if(it!=sob[v].end() && *it<=r){
                x=*it;y=*it;
                x++;y++;
            }
            it=st[v].lower_bound(l);
            if(it!=st[v].end() && (*it)+1<=r){
                x=*it;y=*it+1;
                x++;y++;
            }
            cout<<x<<' '<<y<<'\n';
        }
    }
    return 0;
}

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