제출 #171854

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
171854		RafaelSus	Birthday gift (IZhO18_treearray)	C++14	100 / 100	2291 ms	75768 KiB

treearray

#include <bits/stdc++.h>
 
using namespace std;
const int N = 2e5 + 5;
typedef long long ll;
const ll inf=1e15;
#define pb push_back
const int INF=(0x3f3f3f3f);
 
vector<int>g[N];
int a[N];
int timer,tin[N],tout[N];
int up[20][N];
 
void dfs(int v,int p){
  up[0][v]=p;
  tin[v]=++timer;
  for(int i=1;i<=19;i++){
    up[i][v]=up[i-1][up[i-1][v]];
  }
  for(auto to:g[v])
    if(to!=p)dfs(to,v);
  tout[v]=++timer;
}
 
bool upper(int a,int b){
  return tin[a]<=tin[b]&&tout[a]>=tout[b];
}
 
int lca(int a,int b){
  if(upper(a,b))return a;
  if(upper(b,a))return b;
  for(int i=19;i>=0;--i){
    if(!upper(up[i][a],b)){
      a=up[i][a];
      //cerr<<a<<' ';
    }
  }
  return up[0][a];
}

set<pair<int,int>>s[N];

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);cout.tie(0);
 
  int n,m,q;
  cin>>n>>m>>q;
  for(int i=0;i<n-1;i++){
    int a,b;
    cin>>a>>b;
    g[a].pb(b);
    g[b].pb(a);
  }
  dfs(1,1);
  for(int i=1;i<=m;i++){
    cin>>a[i];
    s[a[i]].insert({i,i});
    if(i>1)s[lca(a[i-1],a[i])].insert({i-1,i});
  }
   
  /*for(int i=1;i<=n;i++){
    cout<<i<<"        ";
    for(auto x:s[i])
      cout<<x.first<<' '<<x.second<<" | ";
    cout<<'\n';
  } */
   
  for(int i=0;i<q;i++){
    int com;
    cin>>com;
    if(com==1){
      int p,v;
      cin>>p>>v;
      s[a[p]].erase({p,p});
      if(p>1)s[lca(a[p-1],a[p])].erase({p-1,p});
      if(p<m)s[lca(a[p],a[p+1])].erase({p,p+1});
      a[p]=v;
      s[a[p]].insert({p,p});
      if(p>1)s[lca(a[p-1],a[p])].insert({p-1,p});
      if(p<m)s[lca(a[p],a[p+1])].insert({p,p+1});
    }else{
      int l,r,v;
      cin>>l>>r>>v;
      int le=-1,ri=-1;
      auto it=s[v].lower_bound({l,0});
      if(it!=s[v].end()){
        if(it->second<=r){
          le=it->first;
          ri=it->second;
        }
        //cerr<<it->first<<' '<<it->second<<'\n';
      }
      cout<<le<<' '<<ri<<'\n';
    }
  }
}

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