제출 #503216

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
503216		Pety	Birthday gift (IZhO18_treearray)	C++14	100 / 100	1043 ms	82544 KiB

treearray

#include <bits/stdc++.h>

#define ll long long
#define ld long double

using namespace std;

const ll MOD = 1e9 + 7;
const ll INF = 1e9;
const int N = 1e5 + 2;

vector<int>G[200002];
int dp[20][200002], a[200002], lvl[200002], n,m , q;

void dfs (int x, int p) {
  dp[0][x] = p;
  lvl[x] = lvl[p] + 1;
  for (int i = 1; (1 << i) <= n; i++)
    dp[i][x] = dp[i - 1][dp[i - 1][x]];
  for (auto it : G[x])
    if (it != p)
      dfs(it, x);
} 

int lca (int x, int y) {
  if (lvl[x] > lvl[y])
    swap(x, y);
  int d = lvl[y] - lvl[x];
  for (int i = 0; (1 << i) <= n; i++)
    if (d & (1 << i))
      y = dp[i][y];
  if (x == y)
    return x;
  for (int i = 19; i >= 0; i--)
    if (dp[i][x] != dp[i][y]) {
      x = dp[i][x];
      y = dp[i][y];
    }
  return dp[0][x];
}

set<int>node[200002];
set<int>lol[200002];

int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  cin >> n >> m >> q;
  for (int i = 1; i < n; i++) {
    int x, y;
    cin >> x >> y;
    G[x].push_back(y);
    G[y].push_back(x);
  }
  dfs(1, 0);
  for (int i = 1; i <= m; i++) {
    cin >> a[i];
    lol[a[i]].insert(i);
    if (i > 1) {
      node[lca(a[i - 1], a[i])].insert(i - 1);
    }
  }
  while (q--) {
    int type;
    cin >> type;
    if (type == 1) {
      int poz, x;
      cin >> poz >> x;
      if (poz > 1) {
        node[lca(a[poz - 1], a[poz])].erase(poz - 1);
        node[lca(x, a[poz - 1])].insert(poz - 1);
      }
      if (poz < m) {
        node[lca(a[poz + 1], a[poz])].erase(poz);
        node[lca(x, a[poz + 1])].insert(poz);
      }
      lol[a[poz]].erase(poz);
      lol[x].insert(poz);
      a[poz] = x;
      
    }
    else {
      int l, r, x;
      cin >> l >> r >> x;
      auto it = node[x].lower_bound(l);
      auto it2 = lol[x].lower_bound(l);
      if (it2 != lol[x].end() && (*it2) <= r) {
        cout << (*it2) << " " << (*it2) << "\n";
      }
      else if (it != node[x].end() && (*it) < r) 
        cout << (*it) << " " << (*it) + 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