Submission #1062009

#	Time	Username	Problem	Language	Result	Execution time	Memory
1062009		Malix	Birthday gift (IZhO18_treearray)	C++14	0 / 100	2 ms	604 KiB

treearray

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef pair<int,int> pi;
typedef vector<pi> pii;
typedef tuple<int,int,int> tii;
typedef vector<ll> li;
typedef vector<li> lii;
 
#define REP(i,a,b) for(int i=a;i<b;i++)
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define LSOne(s) ((s)&(-s))
 
ll INF=1e18+10;
int inf=2e9+10;
ll M=1e9+7;

int n,ms,q,k;
vii a,p;
vi br,as,ae;
vector<map<int,multiset<int>>> st;
int f=0,g=0;

void dfs(int x){
    as[x]=f++;
    for(auto u:a[x]){
        if(as[u]!=-1)continue;
        p[u][0]=x;
        dfs(u);
    }
    ae[x]=g++;
}

bool ances(int x,int y){
    if(y==-1)return 1;
    if(as[x]>=as[y]&&ae[x]<=ae[y])return 1;
    return 0;
}

int LCA(int x,int y){
    if(ances(x,y))return y;
    if(ances(y,x))return x;
    for(int i=k-1;i>=0;i--)if(!ances(x,p[y][i]))y=p[y][i];
    return p[y][0];
}

void build(int x,int l,int r){
    if(l==r){
        st[x][br[l]].insert(l);
        return;
    }
    int m=(l+r)/2;
    build(2*x,l,m);
    build(2*x+1,m+1,r);
    for(auto u:st[2*x])st[x][u.F]=u.S;
    for(auto u:st[2*x+1])for(auto v:u.S)st[x][u.F].insert(v);
    int y=LCA(br[m],br[m+1]);
    st[x][y].insert(m);
}

void update(int x,int l,int r,int p,int v){
    if(l==r){
        st[x][br[p]].erase(st[x][br[p]].find(p));
        st[x][v].insert(p);
        if(l==r)return;
    }
    int m=(l+r)/2;
    if(m>=p)update(2*x,l,m,p,v);
    else update(2*x+1,m+1,r,p,v);
    st[x].clear();
    for(auto u:st[2*x])st[x][u.F]=u.S;
    for(auto u:st[2*x+1])for(auto v:u.S)st[x][u.F].insert(v);
    int y=LCA(v,br[m+1]);
    st[x][y].insert(m);
}

int solve(int x,int l,int r,int a,int b,int v){
    if(a>b)return -1;
    if(l==a&&r==b){
        if(st[x][v].empty())return -1;
        auto it=st[x][v].begin();
        return *it;
    }
    int m=(l+r)/2;
    if(a<=m&&m<=b&&LCA(br[m],br[m+1])==v)return m;
    return max(solve(2*x,l,m,a,min(b,m),v),solve(2*x+1,m+1,r,max(a,m+1),b,v));
}

int main() {   
    cin>>n>>ms>>q;
    k=ceil(log2(n))+1;
    a.resize(n);p.resize(n,vi(k,-1));as.resize(n,-1);ae.resize(n,-1);br.resize(ms);
    REP(i,0,n-1){
        int x,y;cin>>x>>y;
        x--;y--;
        a[x].PB(y);
        a[y].PB(x);
    }
    REP(i,0,ms)cin>>br[i];
    REP(i,0,ms)br[i]--;
    dfs(0);
    REP(j,1,k)REP(i,0,n)if(p[i][j-1]!=-1)p[i][j]=p[p[i][j-1]][j-1];
    st.resize(4*ms+1);
    build(1,0,ms-1);
    while(q--){
        int t;cin>>t;
        if(t==1){
            int x,y;cin>>x>>y;
            x--;y--;
            update(1,0,ms-1,x,y);
            br[x]=y;
        }
        else{
            int l,r,x;cin>>l>>r>>x;
            l--;r--;x--;
            int ans=solve(1,0,ms-1,l,r,x);
            if(ans==-1)ans--;
            if(br[ans]==x||ans==-2)cout<<ans+1<<" "<<ans+1<<"\n";
            else cout<<ans+1<<" "<<ans+2<<"\n";
        }
    }
}

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