제출 #1092036

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1092036		juicy	Birthday gift (IZhO18_treearray)	C++17	0 / 100	12 ms	24156 KiB

treearray

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

const int N = 2e5 + 5, LG = 19;

int n, m, q;
int a[N], tin[N], tout[N], lg[2 * N], spt[LG][2 * N];
set<int> x[N], y[N];
vector<int> g[N];

int cmb(int u, int v) {
  return tin[u] < tin[v] ? u : v;
}

int lca(int u, int v) {
  int l = min(tin[u], tin[v]), r = max(tin[u], tin[v]);
  int k = lg[r - l + 1];
  return cmb(spt[k][l], spt[k][r - (1 << k) + 1]);
}

int timer;

void dfs(int u) {
  spt[0][tin[u] = ++timer] = u;
  for (int v : g[u]) {
    if (!tin[v]) {
      dfs(v);
      spt[0][++timer] = u;
    }
  }
  tout[u] = timer;
}

int main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);
  
  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);
  }
  dfs(1);
  for (int i = 2; i <= timer; ++i) {
    lg[i] = lg[i / 2] + 1;
  }
  for (int j = 1; j < LG; ++j) {
    for (int i = 1; i + (1 << j) - 1 <= timer; ++i) {
      spt[j][i] = cmb(spt[j - 1][i], spt[j - 1][i + (1 << j - 1)]);
    }
  }
  for (int i = 1; i <= n; ++i) {
    x[i].insert(n + 1);
    y[i].insert(n + 1);
  }
  for (int i = 1; i <= m; ++i) {
    cin >> a[i];
  }
  for (int i = 1; i <= m; ++i) {
    x[a[i]].insert(i);
    if (i < m) {
      y[lca(a[i], a[i + 1])].insert(i);
    }
  }
  while (q--) {
    int t; cin >> t;
    if (t == 1) {
      int i, v; cin >> i >> v;
      x[a[i]].erase(i);
      if (i > 1) {
        y[lca(a[i - 1], a[i])].erase(i - 1);
      }
      if (i < m) {
        y[lca(a[i], a[i + 1])].erase(i);
      }
      a[i] = v;
      x[a[i]].insert(i);
      if (i > 1) {
        y[lca(a[i - 1], a[i])].insert(i - 1);
      }
      if (i < m) {
        y[lca(a[i], a[i + 1])].insert(i);
      }
    } else {
      int l, r, v; cin >> l >> r >> v;
      int a = *x[v].lower_bound(l), b = *y[v].lower_bound(l);
      if (a <= r) {
        cout << a << " " << a << "\n";
      } else if (b < r) {
        cout << b << " " << b + 1 << "\n";
      } else {
        cout << "-1 -1\n";
      }
    }
  }
  return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

treearray.cpp: In function 'int main()':
treearray.cpp:56:61: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   56 |       spt[j][i] = cmb(spt[j - 1][i], spt[j - 1][i + (1 << j - 1)]);
      |                                                           ~~^~~

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