Submission #854359

#	Time	Username	Problem	Language	Result	Execution time	Memory
854359		NeroZein	Birthday gift (IZhO18_treearray)	C++17	56 / 100	4016 ms	69960 KiB

treearray

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

#ifdef Nero
#include "Deb.h"
#else
#define deb(...)
#endif

const int LOG = 18; 
const int N = 2e5 + 5; 

int a[N]; 
int lc[N]; 
vector<int> g[N]; 
int dep[N], up[LOG][N]; 
set<int> lco[N], no[N]; 

void dfs(int v, int p) {
  for (int u : g[v]) {
    if (u == p) {
      continue;
    }
    dep[u] = dep[v] + 1; 
    up[0][u] = v;
    for (int j = 1; j < LOG; ++j) {
      up[j][u] = up[j - 1][up[j - 1][u]]; 
    }
    dfs(u, v); 
  }
}

int lca(int u, int v) {
  if (dep[u] < dep[v]) swap(u, v);
  for (int j = 0; j < LOG; ++j) {
    if ((dep[u] - dep[v]) >> j & 1) {
      u = up[j][u];
    }
  }
  if (u == v) return v;
  for (int j = LOG - 1; j >= 0; --j) {
    if (up[j][u] != up[j][v]) {
      u = up[j][u], v = up[j][v]; 
    }
  }
  return up[0][u];
}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n, m, q;
  cin >> n >> m >> q;
  for(int i = 0; i < n - 1; ++i) {
    int u, v;
    cin >> u >> v;
    g[u].push_back(v);
    g[v].push_back(u);
  }
  dfs(1, 1); 
  for (int i = 0; i < m; ++i) {
    cin >> a[i]; 
    no[a[i]].insert(i); 
  }
  for (int i = 0; i < m - 1; ++i) {
    lc[i] = lca(a[i], a[i + 1]); 
    lco[lc[i]].insert(i); 
  }
  while (q--) {
    int t;
    cin >> t;
    if (t == 1) {
      int pos, v;
      cin >> pos >> v;
      pos--; 
      no[a[pos]].erase(pos);
      a[pos] = v; 
      no[a[pos]].insert(pos);
      if (pos < m) {
        lco[lc[pos]].erase(pos);
        lc[pos] = lca(a[pos], a[pos + 1]); 
        lco[lc[pos]].insert(pos);         
      }
      if (pos > 0) {
        lco[lc[pos - 1]].erase(pos - 1);
        lc[pos - 1] = lca(a[pos - 1], a[pos]); 
        lco[lc[pos - 1]].insert(pos - 1); 
      }
    } else {
      int l, r, v;
      cin >> l >> r >> v;
      --l, --r;
      auto s1 = lower_bound(no[v].begin(), no[v].end(), l); 
      if (s1 != no[v].end() && *s1 <= r) {
        cout << *s1 + 1 << ' ' << *s1 + 1 << '\n';
        continue;
      }
      s1 = lower_bound(lco[v].begin(), lco[v].end(), l); 
      if (s1 != lco[v].end() && *s1 < r) {
        cout << *s1 + 1 << ' ' << *s1 + 2 << '\n';
      } else {
        cout << -1 << ' ' << -1 << '\n';
      }
    }
  }
  return 0;
}

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