Submission #522716

#	Time	Username	Problem	Language	Result	Execution time	Memory
522716		inluminas	Birthday gift (IZhO18_treearray)	C++17	100 / 100	1197 ms	86444 KiB

treearray

#include"bits/stdc++.h"
using namespace std;
 
#define ll long long
#define endl "\n"
#define fastio ios_base::sync_with_stdio(false)
#define inf LLONG_MAX

const int lmt=2e5+10;
vector<int>adj[lmt];
int lvl[lmt],par[lmt][20];
set<int>s[lmt],pre[lmt];

void dfs(int u,int p){
  for(int v:adj[u]){
    if(v==p) continue;
    lvl[v]=lvl[u]+1;
    par[v][0]=u;
    dfs(v,u);
  }
}

int lca(int p,int q){
  if(lvl[p]<lvl[q]) swap(p,q);
  for(int i=19;i>=0;i--){
    if(lvl[p]-(1<<i)>=lvl[q]){
      p=par[p][i];
    }
  }
  if(p==q) return p;
  for(int i=19;i>=0;i--){
    if(par[p][i]!=-1 && par[p][i]!=par[q][i]){
      p=par[p][i],q=par[q][i];
    }
  }
  return par[p][0];
}

int main(){
  fastio;

  for(int i=0;i<lmt;i++){
    for(int j=0;j<20;j++) par[i][j]=-1;
  }

  int n,m,k;
  cin>>n>>m>>k;
  for(int i=1;i<n;i++){
    int u,v;
    cin>>u>>v;
    adj[u].push_back(v);
    adj[v].push_back(u);
  }
  dfs(1,0);
  for(int j=1;j<20;j++){
    for(int i=1;i<=n;i++){
      if(par[i][j-1]==-1) continue;
      par[i][j]=par[par[i][j-1]][j-1];
    }
  }

  int a[m+1];
  for(int i=1;i<=m;i++){
    cin>>a[i];
    pre[a[i]].insert(i);
    if(i==1) continue;
    int p=lca(a[i-1],a[i]);
    s[p].insert(i-1);
  }

  while(k--){
    int t;
    cin>>t;
    if(t==1){
      int pos,v;
      cin>>pos>>v;
      pre[a[pos]].erase(pos);
      pre[v].insert(pos);
      if(pos>1) s[lca(a[pos-1],a[pos])].erase(pos-1);
      if(pos<m) s[lca(a[pos],a[pos+1])].erase(pos);
      a[pos]=v;
      if(pos>1) s[lca(a[pos-1],a[pos])].insert(pos-1);
      if(pos<m) s[lca(a[pos],a[pos+1])].insert(pos);
    }else{
      int l,r,v;
      cin>>l>>r>>v;
      auto it=s[v].lower_bound(l);
      if(it!=s[v].end() && (*it)+1<=r) cout<<(*it)<<" "<<(*it)+1<<endl;
      else{
        it=pre[v].lower_bound(l);
        if(it!=pre[v].end() && (*it)<=r) cout<<(*it)<<" "<<(*it)<<endl;
        else cout<<-1<<" "<<-1<<endl;
      }
    }
  }
  return 0;
}

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