제출 #696086

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
696086		Abrar_Al_Samit	Birthday gift (IZhO18_treearray)	C++17	100 / 100	1120 ms	83928 KiB

treearray

#include<bits/stdc++.h>
using namespace std;

const int nax = 2e5 + 3;

vector<int>g[nax];

int n, m, q;
int a[nax];
int sp[nax][18];
int tt(0);
int st[nax], en[nax], dep[nax];
set<int>S[nax], T[nax];

bool anc(int x, int y) {
  return st[x]<=st[y] && en[x]>=en[y];
}
int getlca(int x, int y) {
  if(x==0) return y;
  if(y==0) return x;

  for(int j=17; j>=0; --j) {
    if(!anc(sp[x][j], y)) {
      x = sp[x][j];
    }
  }
  if(!anc(x, y)) x = sp[x][0];
  return x;
}
void DFS(int v, int par = 1) {
  dep[v] = 1+dep[par];
  st[v] = tt++;

  sp[v][0] = par;
  for(int j=1; j<18; ++j) {
    sp[v][j] = sp[sp[v][j-1]][j-1];
  }

  for(int u : g[v]) if(u!=par) {
    DFS(u, v);
  }
  en[v] = tt++;
}
void PlayGround() {
  cin>>n>>m>>q;

  for(int i=1; i<n; ++i) {
    int u, v;
    cin>>u>>v;
    g[u].push_back(v);
    g[v].push_back(u);
  }
  for(int i=1; i<=m; ++i) {
    cin>>a[i];
  }

  dep[1] = -1;
  DFS(1);


  for(int i=1; i<=m; ++i) {
    S[a[i]].insert(i);

    if(i<m) {
      T[getlca(a[i], a[i+1])].insert(i+1);
    }
  }

  while(q--) {
    int t;
    cin>>t;
    if(t==1) {
      int pos, v;
      cin>>pos>>v;

      S[a[pos]].erase(pos);
      S[v].insert(pos);

      if(pos<m) {
        T[getlca(a[pos], a[pos+1])].erase(pos+1);
        T[getlca(a[pos+1], v)].insert(pos+1);
      }
      if(pos>1) {
        T[getlca(a[pos], a[pos-1])].erase(pos);
        T[getlca(a[pos-1], v)].insert(pos);
      }
      a[pos] = v;

    } else {
      int l, r, v;
      cin>>l>>r>>v;

      if(S[v].lower_bound(l)!=S[v].end() && *S[v].lower_bound(l)<=r) {
        cout<<*S[v].lower_bound(l)<<' '<<*S[v].lower_bound(l)<<'\n';
        continue;
      }
      if(T[v].lower_bound(l+1)!=T[v].end() && *T[v].lower_bound(l+1)<=r) {
        cout<<*T[v].lower_bound(l+1)-1<<' '<<*T[v].lower_bound(l+1)<<'\n';
        continue;
      }
      cout<<"-1 -1\n";
    } 
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  PlayGround();
  return 0;
}

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