Advertisement
Guest User

hld_template

a guest
Jun 20th, 2020
1,568
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. template<int size, int lg, typename seg_t = long long>
  2. struct hld {
  3. vector<int> edges[size];
  4. int bigchild[size];
  5. int sz[size];
  6. int depth[size];
  7. int chain[size];
  8. int label[size], label_time;
  9. int par[size];
  10.  
  11. int lca_lift[size][lg];
  12.  
  13. seg_t seg_tree[4 * size];
  14. seg_t seg_lazy[4 * size];
  15.  
  16. int N;
  17.  
  18. /* ----------- segment tree ----------- */
  19.  
  20. /* CHANGE THIS SECTION BY PROBLEM */
  21. inline seg_t seg_combine(seg_t a, seg_t b) {
  22. return a ^ b;
  23. }
  24.  
  25. inline seg_t seg_lazy_apply(seg_t lazy_val, seg_t new_val) {
  26. return new_val;
  27. }
  28.  
  29. inline seg_t seg_lazy_func(seg_t cur_val, seg_t lazy_val, int l, int r) {
  30. return lazy_val;
  31. }
  32.  
  33. const seg_t seg_sentinel = 0;
  34. const seg_t seg_lazy_sentinel = -1;
  35. const seg_t seg_init_val = 0;
  36. /* END SECTION */
  37.  
  38. seg_t seg_query_header(int l, int r) {
  39. return seg_query_rec(0, 0, N - 1, l, r);
  40. }
  41.  
  42. seg_t seg_query_rec(int i, int tl, int tr, int ql, int qr) {
  43. seg_eval_lazy(i, tl, tr);
  44.  
  45. if (ql <= tl && tr <= qr) return seg_tree[i];
  46. if (tl > tr || tr < ql || qr < tl) return seg_sentinel;
  47.  
  48. int mid = (tl + tr) / 2;
  49. seg_t a = seg_query_rec(2 * i + 1, tl, mid, ql, qr);
  50. seg_t b = seg_query_rec(2 * i + 2, mid + 1, tr, ql, qr);
  51. return seg_combine(a, b);
  52. }
  53.  
  54. void seg_update_header(int l, int r, seg_t v) {
  55. seg_update_rec(0, 0, N - 1, l, r, v);
  56. }
  57.  
  58. seg_t seg_update_rec(int i, int tl, int tr, int ql, int qr, seg_t v) {
  59. seg_eval_lazy(i, tl, tr);
  60.  
  61. if (tl > tr || tr < ql || qr < tl) return seg_tree[i];
  62. if (ql <= tl && tr <= qr) {
  63. seg_lazy[i] = seg_lazy_apply(seg_lazy[i], v);
  64. seg_eval_lazy(i, tl, tr);
  65. return seg_tree[i];
  66. }
  67. if (tl == tr) return seg_tree[i];
  68.  
  69. int mid = (tl + tr) / 2;
  70. seg_t a = seg_update_rec(2 * i + 1, tl, mid, ql, qr, v);
  71. seg_t b = seg_update_rec(2 * i + 2, mid + 1, tr, ql, qr, v);
  72. return seg_tree[i] = seg_combine(a, b);
  73. }
  74.  
  75. void seg_eval_lazy(int i, int l, int r) {
  76. if (seg_lazy[i] == seg_lazy_sentinel) return;
  77.  
  78. seg_tree[i] = seg_lazy_func(seg_tree[i], seg_lazy[i], l, r);
  79.  
  80. if (l != r) {
  81. seg_lazy[i * 2 + 1] = seg_lazy_apply(seg_lazy[i * 2 + 1], seg_lazy[i]);
  82. seg_lazy[i * 2 + 2] = seg_lazy_apply(seg_lazy[i * 2 + 2], seg_lazy[i]);
  83. }
  84.  
  85. seg_lazy[i] = seg_lazy_sentinel;
  86. }
  87.  
  88. /* ----------- init phase 1 ----------- */
  89. /* initialize segtree, clear edges, etc. */
  90.  
  91. void init_arrays(int n) {
  92. // everything not initialized doesn't need to be
  93. N = n;
  94. for (int i = 0; i < N; i++) {
  95. edges[i].clear();
  96. chain[i] = i;
  97. }
  98.  
  99. for (int i = 0; i < 4 * N; i++) {
  100. seg_tree[i] = seg_init_val;
  101. seg_lazy[i] = seg_lazy_sentinel;
  102. }
  103. }
  104.  
  105. /* ----------- init phase 2 ----------- */
  106. /* put edges in */
  107.  
  108. void add_edge(int u, int v) {
  109. edges[u].push_back(v);
  110. edges[v].push_back(u);
  111. }
  112.  
  113. /* ----------- init phase 3 ----------- */
  114. /* build the lca and hld stuff */
  115.  
  116. void init_tree(seg_t* arr, int root = 0) {
  117. // lca
  118. lca_dfs(root, -1);
  119.  
  120. // size, compute biggest children
  121. dfs_size(root, -1, 0);
  122.  
  123. // compute chains
  124. dfs_chains(root, -1);
  125.  
  126. // label nodes
  127. label_time = 0;
  128. dfs_labels(arr, root, -1);
  129. }
  130.  
  131. void lca_dfs(int v, int par) {
  132. lca_lift[v][0] = par;
  133.  
  134. for (int i = 1; i < lg; i++) {
  135. if (lca_lift[v][i - 1] == -1) lca_lift[v][i] = -1;
  136. else lca_lift[v][i] = lca_lift[lca_lift[v][i - 1]][i - 1];
  137. }
  138.  
  139. for (int x: edges[v]) {
  140. if (x != par) {
  141. lca_dfs(x, v);
  142. }
  143. }
  144. }
  145.  
  146. void dfs_size(int v, int p, int d) {
  147. sz[v] = 1;
  148. depth[v] = d;
  149. par[v] = p;
  150. int bigc = -1, bigv = -1;
  151.  
  152. for (int x: edges[v]) {
  153. if (x != p) {
  154. dfs_size(x, v, d + 1);
  155. sz[v] += sz[x];
  156. if (sz[x] > bigv) {
  157. bigc = x;
  158. bigv = sz[x];
  159. }
  160. }
  161. }
  162.  
  163. bigchild[v] = bigc;
  164. }
  165.  
  166. void dfs_chains(int v, int p) {
  167. if (bigchild[v] != -1) {
  168. chain[bigchild[v]] = chain[v];
  169. }
  170.  
  171. for (int x: edges[v]) {
  172. if (x != p) {
  173. dfs_chains(x, v);
  174. }
  175. }
  176. }
  177.  
  178. void dfs_labels(seg_t* arr, int v, int p) {
  179. label[v] = label_time++;
  180. seg_update_header(label[v], label[v], arr[v]);
  181.  
  182. if (bigchild[v] != -1) {
  183. dfs_labels(arr, bigchild[v], v);
  184. }
  185.  
  186. for (int x: edges[v]) {
  187. if (x != p && x != bigchild[v]) {
  188. dfs_labels(arr, x, v);
  189. }
  190. }
  191. }
  192.  
  193. /* ----------- init phase 4 ----------- */
  194. /* usage */
  195.  
  196. int lca(int a, int b) {
  197. if (depth[a] < depth[b]) swap(a, b);
  198. int d = depth[a] - depth[b];
  199. int v = get_kth_ancestor(a, d);
  200. if (v == b) {
  201. return v;
  202. } else {
  203. for (int i = lg - 1; i >= 0; i--) {
  204. if (lca_lift[v][i] != lca_lift[b][i]) {
  205. v = lca_lift[v][i];
  206. b = lca_lift[b][i];
  207. }
  208. }
  209. return lca_lift[b][0];
  210. }
  211. }
  212.  
  213. int get_kth_ancestor(int v, int k) {
  214. for (int i = lg - 1; i >= 0; i--) {
  215. if (v == -1) return v;
  216. if ((1 << i) <= k) {
  217. v = lca_lift[v][i];
  218. k -= (1 << i);
  219. }
  220. }
  221. return v;
  222. }
  223.  
  224. /* excludes p */
  225. seg_t query_chain(int v, int p) {
  226. seg_t val = seg_sentinel;
  227. while (depth[p] < depth[v]) {
  228. int top = chain[v];
  229. if (depth[top] <= depth[p]) {
  230. int diff = depth[v] - depth[p];
  231. top = get_kth_ancestor(v, diff - 1);
  232. }
  233. val = seg_combine(val, seg_query_header(label[top], label[v]));
  234. v = par[top];
  235. }
  236. return val;
  237. }
  238.  
  239. seg_t query(int u, int v) {
  240. int lc = lca(u, v);
  241. seg_t val = seg_combine(query_chain(u, lc), query_chain(v, lc));
  242. return seg_combine(val, seg_query_header(label[lc], label[lc]));
  243. }
  244.  
  245. /* excludes p */
  246. void update_chain(int v, int p, seg_t val) {
  247. while (depth[p] < depth[v]) {
  248. int top = chain[v];
  249. if (depth[top] <= depth[p]) {
  250. int diff = depth[v] - depth[p];
  251. top = get_kth_ancestor(v, diff - 1);
  252. }
  253. seg_update_header(label[top], label[v], val);
  254. v = par[top];
  255. }
  256. }
  257.  
  258. void update(int u, int v, seg_t val) {
  259. int lc = lca(u, v);
  260. update_chain(u, lc, val);
  261. update_chain(v, lc, val);
  262. seg_update_header(label[lc], label[lc], val);
  263. }
  264. };
Advertisement
RAW Paste Data Copied
Advertisement