#686610 (C++17) No.1641 Tree Xor Query

提出ソース

結果

問題	No.1641 Tree Xor Query
ユーザー	Haar
提出日時	2021-08-06 22:05:27
言語	C++17 (gcc 13.2.0 + boost 1.83.0)
結果	AC
実行時間	101 ms / 5,000 ms
コード長	11,297 bytes
コンパイル時間	2,700 ms
コンパイル使用メモリ	219,256 KB
実行使用メモリ	26,148 KB
最終ジャッジ日時	2023-10-17 03:28:10
合計ジャッジ時間	3,920 ms
ジャッジサーバーID （参考情報）	judge13 / judge11

このコードへのチャレンジ（β）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 4,348 KB
testcase_01	AC	2 ms 4,348 KB
testcase_02	AC	2 ms 4,348 KB
testcase_03	AC	2 ms 4,348 KB
testcase_04	AC	2 ms 4,348 KB
testcase_05	AC	2 ms 4,348 KB
testcase_06	AC	2 ms 4,348 KB
testcase_07	AC	2 ms 4,348 KB
testcase_08	AC	2 ms 4,348 KB
testcase_09	AC	2 ms 4,348 KB
testcase_10	AC	2 ms 4,348 KB
testcase_11	AC	2 ms 4,348 KB
testcase_12	AC	2 ms 4,348 KB
testcase_13	AC	101 ms 26,148 KB
testcase_14	AC	100 ms 26,148 KB
testcase_15	AC	4 ms 4,348 KB
testcase_16	AC	9 ms 4,764 KB
testcase_17	AC	7 ms 4,492 KB
testcase_18	AC	7 ms 4,500 KB
testcase_19	AC	4 ms 4,348 KB
testcase_20	AC	78 ms 20,496 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <bits/stdc++.h>

#ifdef DEBUG
#include <Mylib/Debug/debug.cpp>
#else
#define dump(...) ((void)0)
#endif

template <typename T, typename U>
bool chmin(T &a, const U &b) {
  return (a > b ? a = b, true : false);
}

template <typename T, typename U>
bool chmax(T &a, const U &b) {
  return (a < b ? a = b, true : false);
}

template <typename T, size_t N, typename U>
void fill_array(T (&a)[N], const U &v) {
  std::fill((U *) a, (U *) (a + N), v);
}

template <typename T, size_t N, size_t I = N>
auto make_vector(const std::array<int, N> &a, T value = T()) {
  static_assert(I >= 1);
  static_assert(N >= 1);
  if constexpr (I == 1) {
      return std::vector<T>(a[N - I], value);
    } else {
    return std::vector(a[N - I], make_vector<T, N, I - 1>(a, value));
  }
}

template <typename T>
std::ostream &operator<<(std::ostream &s, const std::vector<T> &a) {
  for (auto it = a.begin(); it != a.end(); ++it) {
    if (it != a.begin()) s << " ";
    s << *it;
  }
  return s;
}

template <typename T>
std::istream &operator>>(std::istream &s, std::vector<T> &a) {
  for (auto &x : a) s >> x;
  return s;
}

std::string YesNo(bool value) { return value ? "Yes" : "No"; }
std::string YESNO(bool value) { return value ? "YES" : "NO"; }
std::string yesno(bool value) { return value ? "yes" : "no"; }

template <typename T>
void putl(const T &value) {
  std::cout << value << "\n";
}

template <typename Head, typename... Tail>
void putl(const Head head, const Tail &... tail) {
  std::cout << head << " ";
  putl(tail...);
}

namespace haar_lib {
  template <typename T>
  struct edge {
    int from, to;
    T cost;
    int index = -1;
    edge() {}
    edge(int from, int to, T cost) : from(from), to(to), cost(cost) {}
    edge(int from, int to, T cost, int index) : from(from), to(to), cost(cost), index(index) {}
  };

  template <typename T>
  struct graph {
    using weight_type = T;
    using edge_type   = edge<T>;

    std::vector<std::vector<edge<T>>> data;

    auto& operator[](size_t i) { return data[i]; }
    const auto& operator[](size_t i) const { return data[i]; }

    auto begin() const { return data.begin(); }
    auto end() const { return data.end(); }

    graph() {}
    graph(int N) : data(N) {}

    bool empty() const { return data.empty(); }
    int size() const { return data.size(); }

    void add_edge(int i, int j, T w, int index = -1) {
      data[i].emplace_back(i, j, w, index);
    }

    void add_undirected(int i, int j, T w, int index = -1) {
      add_edge(i, j, w, index);
      add_edge(j, i, w, index);
    }

    template <size_t I, bool DIRECTED = true, bool WEIGHTED = true>
    void read(int M) {
      for (int i = 0; i < M; ++i) {
        int u, v;
        std::cin >> u >> v;
        u -= I;
        v -= I;
        T w = 1;
        if (WEIGHTED) std::cin >> w;
        if (DIRECTED)
          add_edge(u, v, w, i);
        else
          add_undirected(u, v, w, i);
      }
    }
  };

  template <typename T>
  using tree = graph<T>;
}  // namespace haar_lib


namespace haar_lib {
  template <typename T>
  class hl_decomposition {
    int n_;

    std::vector<int> sub_,  // subtree size
      par_,               // parent id
      head_,              // chain head id
      id_,                // id[original id] = hld id
      rid_,               // rid[hld id] = original id
      next_,              // next node in a chain
      end_;               //

    int dfs_sub(tree<T> &tr, int cur, int p) {
      par_[cur] = p;
      int t     = 0;
      for (auto &e : tr[cur]) {
        if (e.to == p) continue;
        sub_[cur] += dfs_sub(tr, e.to, cur);
        if (sub_[e.to] > t) {
          t          = sub_[e.to];
          next_[cur] = e.to;
          std::swap(e, tr[cur][0]);
        }
      }
      return sub_[cur];
    }

    void dfs_build(const tree<T> &tr, int cur, int &i) {
      id_[cur] = i;
      rid_[i]  = cur;
      ++i;

      for (auto &e : tr[cur]) {
        if (e.to == par_[cur]) continue;
        head_[e.to] = (e.to == tr[cur][0].to ? head_[cur] : e.to);
        dfs_build(tr, e.to, i);
      }

      end_[cur] = i;
    }

  public:
    hl_decomposition() {}
    hl_decomposition(tree<T> tr, int root) : n_(tr.size()), sub_(n_, 1), par_(n_, -1), head_(n_), id_(n_), rid_(n_), next_(n_, -1), end_(n_, -1) {
      dfs_sub(tr, root, -1);
      int i = 0;
      dfs_build(tr, root, i);
    }

    std::vector<std::tuple<int, int, bool>> path_query_vertex(int x, int y) const {
      std::vector<std::tuple<int, int, bool>> ret;
      const int w = lca(x, y);

      {
        int y  = w;
        bool d = true;
        while (1) {
          if (id_[x] > id_[y]) std::swap(x, y), d = not d;
          int l = std::max(id_[head_[y]], id_[x]), r = id_[y] + 1;
          if (l != r) ret.emplace_back(l, r, d);
          if (head_[x] == head_[y]) break;
          y = par_[head_[y]];
        }
      }

      x = y;
      y = w;

      {
        std::vector<std::tuple<int, int, bool>> temp;
        bool d = false;
        while (1) {
          if (id_[x] > id_[y]) std::swap(x, y), d = not d;
          int l = std::max({id_[head_[y]], id_[x], id_[w] + 1}), r = id_[y] + 1;
          if (l != r) temp.emplace_back(l, r, d);
          if (head_[x] == head_[y]) break;
          y = par_[head_[y]];
        }

        std::reverse(temp.begin(), temp.end());
        ret.insert(ret.end(), temp.begin(), temp.end());
      }

      return ret;
    }

    std::vector<std::pair<int, int>> path_query_edge(int x, int y) const {
      std::vector<std::pair<int, int>> ret;
      while (1) {
        if (id_[x] > id_[y]) std::swap(x, y);
        if (head_[x] == head_[y]) {
          if (x != y) ret.emplace_back(id_[x] + 1, id_[y] + 1);
          break;
        }
        ret.emplace_back(id_[head_[y]], id_[y] + 1);
        y = par_[head_[y]];
      }
      return ret;
    }

    std::pair<int, int> subtree_query_edge(int x) const {
      return {id_[x] + 1, end_[x]};
    }

    std::pair<int, int> subtree_query_vertex(int x) const {
      return {id_[x], end_[x]};
    }

    int get_edge_id(int u, int v) const {  // 辺に対応するid
      if (par_[u] == v) return id_[u];
      if (par_[v] == u) return id_[v];
      return -1;
    }

    int parent(int x) const { return par_[x]; };

    int lca(int u, int v) const {
      while (1) {
        if (id_[u] > id_[v]) std::swap(u, v);
        if (head_[u] == head_[v]) return u;
        v = par_[head_[v]];
      }
    }

    int get_id(int x) const {
      return id_[x];
    }
  };
}  // namespace haar_lib

namespace haar_lib {
  template <typename Monoid>
  class segment_tree {
  public:
    using value_type = typename Monoid::value_type;

  private:
    Monoid M_;
    int depth_, size_, hsize_;
    std::vector<value_type> data_;

  public:
    segment_tree() {}
    segment_tree(int n) : depth_(n > 1 ? 32 - __builtin_clz(n - 1) + 1 : 1),
                          size_(1 << depth_),
                          hsize_(size_ / 2),
                          data_(size_, M_()) {}

    auto operator[](int i) const {
      assert(0 <= i and i < hsize_);
      return data_[hsize_ + i];
    }

    auto fold(int l, int r) const {
      assert(0 <= l and l <= r and r <= hsize_);
      value_type ret_left  = M_();
      value_type ret_right = M_();

      int L = l + hsize_, R = r + hsize_;
      while (L < R) {
        if (R & 1) ret_right = M_(data_[--R], ret_right);
        if (L & 1) ret_left = M_(ret_left, data_[L++]);
        L >>= 1, R >>= 1;
      }

      return M_(ret_left, ret_right);
    }

    auto fold_all() const {
      return data_[1];
    }

    void set(int i, const value_type &x) {
      assert(0 <= i and i < hsize_);
      i += hsize_;
      data_[i] = x;
      while (i > 1) i >>= 1, data_[i] = M_(data_[i << 1 | 0], data_[i << 1 | 1]);
    }

    void update(int i, const value_type &x) {
      assert(0 <= i and i < hsize_);
      i += hsize_;
      data_[i] = M_(data_[i], x);
      while (i > 1) i >>= 1, data_[i] = M_(data_[i << 1 | 0], data_[i << 1 | 1]);
    }

    template <typename T>
    void init_with_vector(const std::vector<T> &val) {
      data_.assign(size_, M_());
      for (int i = 0; i < (int) val.size(); ++i) data_[hsize_ + i] = val[i];
      for (int i = hsize_; --i >= 1;) data_[i] = M_(data_[i << 1 | 0], data_[i << 1 | 1]);
    }

    template <typename T>
    void init(const T &val) {
      init_with_vector(std::vector<value_type>(hsize_, val));
    }

  private:
    template <bool Lower, typename F>
    int bound(const int l, const int r, value_type x, F f) const {
      std::vector<int> pl, pr;
      int L = l + hsize_;
      int R = r + hsize_;
      while (L < R) {
        if (R & 1) pr.push_back(--R);
        if (L & 1) pl.push_back(L++);
        L >>= 1, R >>= 1;
      }

      std::reverse(pr.begin(), pr.end());
      pl.insert(pl.end(), pr.begin(), pr.end());

      value_type a = M_();

      for (int i : pl) {
        auto b = M_(a, data_[i]);

        if ((Lower and not f(b, x)) or (not Lower and f(x, b))) {
          while (i < hsize_) {
            const auto c = M_(a, data_[i << 1 | 0]);
            if ((Lower and not f(c, x)) or (not Lower and f(x, c))) {
              i = i << 1 | 0;
            } else {
              a = c;
              i = i << 1 | 1;
            }
          }

          return i - hsize_;
        }

        a = b;
      }

      return r;
    }

  public:
    template <typename F = std::less<value_type>>
    int lower_bound(int l, int r, value_type x, F f = F()) const {
      return bound<true>(l, r, x, f);
    }

    template <typename F = std::less<value_type>>
    int upper_bound(int l, int r, value_type x, F f = F()) const {
      return bound<false>(l, r, x, f);
    }
  };
}  // namespace haar_lib

namespace haar_lib {
  template <typename T>
  struct bitxor_monoid {
    using value_type = T;
    value_type operator()() const { return 0; }
    value_type operator()(value_type a, value_type b) const { return a ^ b; }
  };
}  // namespace haar_lib



namespace haar_lib {}

namespace solver {
  using namespace haar_lib;

  constexpr int m1000000007 = 1000000007;
  constexpr int m998244353  = 998244353;

  void init() {
    std::cin.tie(0);
    std::ios::sync_with_stdio(false);
    std::cout << std::fixed << std::setprecision(12);
    std::cerr << std::fixed << std::setprecision(12);
    std::cin.exceptions(std::ios_base::failbit);
  }

  void solve() {
    int N, Q; std::cin >> N >> Q;
    std::vector<int> C(N); std::cin >> C;
    graph<int> g(N);
    g.read<1,false,false>(N - 1);

    auto hld = hl_decomposition(g, 0);
    auto seg = segment_tree<bitxor_monoid<int>>(N);

    for (int i = 0; i < N; ++i) {
      seg.update(hld.get_id(i), C[i]);
    }

    while (Q--) {
      int t, x, y; std::cin >> t >> x >> y;
      --x;

      if (t == 1) {
        seg.update(hld.get_id(x), y);
      }
      else{
        auto [l, r] = hld.subtree_query_vertex(x);
        auto ans = seg.fold(l, r);

        std::cout << ans << "\n";
      }
    }
  }
}

int main() {
  solver::init();
  while (true) {
    try {
      solver::solve();
      std::cout << std::flush;
      std::cerr << std::flush;
    } catch (const std::istream::failure &e) {
      break;
    } catch (...) {
      break;
    }
  }
  return 0;
}

yukicoder

結果

テストケース

ソースコード