Submission #637996

#	Time	Username	Problem	Language	Result	Execution time	Memory
637996		tvladm2009	Birthday gift (IZhO18_treearray)	C++14	100 / 100	1040 ms	84184 KiB

treearray

#include <bits/stdc++.h>

const int MAX_N = 2 * 1e5;
const int MAX_L = 19;

std::vector<int> g[MAX_N + 1];
int a[MAX_N + 1], up[MAX_N + 1][MAX_L + 1], l[MAX_N + 1], r[MAX_N + 1];
std::set<int> one[MAX_N + 1], two[MAX_N + 1];
int t = 0;

void dfs(int u, int p) {
  up[u][0] = p;
  for (int i = 1; i <= MAX_L; i++) {
    up[u][i] = up[up[u][i - 1]][i - 1];
  }
  l[u] = ++t;
  for (int v : g[u]) {
    if (v != p) {
      dfs(v, u);
    }
  }
  r[u] = ++t;
}

bool is_ancestor(int u, int v) {
  return l[u] <= l[v] && r[v] <= r[u];
}

int lca(int u, int v) {
  if (is_ancestor(u, v)) {
    return v;
  } else if (is_ancestor(v, u)) {
    return u;
  }
  for (int i = MAX_L; i >= 0; i--) {
    if (!is_ancestor(up[u][i], v)) {
      u = up[u][i];
    }
  }
  return up[u][0];
}

int main() {
  std::ios_base::sync_with_stdio(0);
  std::cin.tie(0);
  int n, m, q;
  std::cin >> n >> m >> q;
  for (int i = 1; i <= n - 1; i++) {
    int x, y;
    std::cin >> x >> y;
    g[x].push_back(y);
    g[y].push_back(x);
  }
  dfs(1, 1);
  for (int i = 1; i <= m; i++) {
    std::cin >> a[i];
    one[a[i]].insert(i);
    if (i > 1) {
      two[lca(a[i - 1], a[i])].insert(i - 1);
    }
  }
  for (int i = 1; i <= q; i++) {
    int type = 0;
    std::cin >> type;
    if (type == 1) {
      int pos, v;
      std::cin >> pos >> v;
      one[a[pos]].erase(pos);
      if (pos > 1) {
        two[lca(a[pos - 1], a[pos])].erase(pos - 1);
      }
      if (pos < m) {
        two[lca(a[pos], a[pos + 1])].erase(pos);
      }
      a[pos] = v;
      one[a[pos]].insert(pos);
      if (pos > 1) {
        two[lca(a[pos - 1], a[pos])].insert(pos - 1);
      }
      if (pos < m) {
        two[lca(a[pos], a[pos + 1])].insert(pos);
      }
    } else {
      int l, r, v;
      std::cin >> l >> r >> v;
      auto it = one[v].lower_bound(l);
      if (it != one[v].end() && (*it) <= r) {
        std::cout << (*it) << " " << (*it) << "\n";
        continue;
      }
      it = two[v].lower_bound(l);
      if (it != two[v].end() && (*it) + 1 <= r) {
        std::cout << (*it) << " " << (*it) + 1 << "\n";
        continue;
      }
      std::cout << "-1 -1\n";
    }
  }
  return 0;
}

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