Submission #395419

#	Time	Username	Problem	Language	Result	Execution time	Memory
395419		rama_pang	Birthday gift (IZhO18_treearray)	C++17	100 / 100	1936 ms	79268 KiB

treearray

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

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);

  // Solution:
  // If A[] is a sequence, and LCA[] is all possible LCA(x, y) = LCA(A[x], A[x + 1], ..., A[y])
  // Then appending A[] with Z will only add possible LCA = LCA(A[-1], Z).
  // Why?
  // Consider W = LCA(A[-1], Z). Then A[-1] is in some subtree of child of W, Z is in another subtree of W.
  // All other possible LCA involving the new Z must be some ancestor of W. Let this ancestor be L, and
  // the segment be LCA(Y...Z).
  // But then, LCA(Y + 1, Z) != L, so Y and (Y + 1) must be in a different subtree of child of L, so
  // it is already added (LCA(Y, Y+1)).
  //
  // So, we only need to care about 2 adjacent elements in A[]. We can check the LCA() with binary lifting.
  // Time complexity: O(N log N).

  int N, M, Q;
  cin >> N >> M >> Q;

  vector<vector<int>> adj(N);
  for (int i = 1; i < N; i++) {
    int u, v;
    cin >> u >> v;
    u--, v--;
    adj[u].emplace_back(v);
    adj[v].emplace_back(u);
  }

  const int LOG = 18;
  vector<int> depth(N);
  vector<vector<int>> lift(LOG, vector<int>(N, -1));

  const auto Dfs = [&](const auto &self, int u, int p) -> void {
    lift[0][u] = p;
    for (int i = 1; i < LOG; i++) {
      lift[i][u] = lift[i - 1][u] == -1 ? -1 : lift[i - 1][lift[i - 1][u]];
    }
    for (auto v : adj[u]) if (v != p) {
      depth[v] = depth[u] + 1;
      self(self, v, u);
    }
  };
  Dfs(Dfs, 0, -1);

  const auto Lca = [&](int x, int y) {
    if (depth[x] > depth[y]) swap(x, y);

    int diff = depth[y] - depth[x];
    for (int i = 0; i < LOG; i++) {
      if ((diff >> i) & 1) {
        y = lift[i][y];
      }
    }

    assert(depth[x] == depth[y]);

    for (int i = LOG - 1; i >= 0; i--) {
      if (lift[i][x] != lift[i][y]) {
        x = lift[i][x];
        y = lift[i][y];
      }
    }
    return x == y ? x : lift[0][x];
  };

  vector<int> A(M);
  for (int i = 0; i < M; i++) {
    cin >> A[i];
    A[i]--;
  }

  vector<set<pair<int, int>>> ans(N);
  for (int i = 0; i < M; i++) {
    ans[A[i]].emplace(i, i);
  }
  for (int i = 1; i < M; i++) {
    ans[Lca(A[i - 1], A[i])].emplace(i - 1, i);
  }

  while (Q--) {
    int type;
    cin >> type;
    if (type == 1) {
      int i, v;
      cin >> i >> v;
      i--, v--;

      ans[A[i]].erase({i, i});
      if (i - 1 >= 0) ans[Lca(A[i - 1], A[i])].erase({i - 1, i});
      if (i + 1 <  M) ans[Lca(A[i], A[i + 1])].erase({i, i + 1});

      A[i] = v;

      ans[A[i]].insert({i, i});
      if (i - 1 >= 0) ans[Lca(A[i - 1], A[i])].insert({i - 1, i});
      if (i + 1 <  M) ans[Lca(A[i], A[i + 1])].insert({i, i + 1});
    } else if (type == 2) {
      int l, r, v;
      cin >> l >> r >> v;
      l--, r--, v--;
      auto it = ans[v].lower_bound({l, -1});
      if (it != end(ans[v]) && it->second <= r) {
        cout << it->first + 1 << ' ' << it->second + 1 << '\n';
      } else {
        cout << "-1 -1\n";
      }
    }
  }
  return 0;
}

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