Advertisement
Aslanov01

Segment tree with struct and push

Feb 12th, 2024 (edited)
766
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.26 KB | Source Code | 0 0
  1. struct node {
  2.     int x, y, z;//можно называть любым способом
  3. };
  4. node t[4 * N], upd[4 * N];
  5. node merge(node a, node b) {
  6.     node res;
  7.     res.x = //???
  8.     res.y = //???
  9.     res.z = //??? зависит от задачи
  10.     return res;
  11. }
  12. void build(int v, int tl, int tr) {
  13.     if (tl == tr) {
  14.         t[v] = {?, ?, ?};
  15.         return;
  16.     }
  17.     int mid = (tl + tr) / 2;
  18.     build(v * 2, tl, mid), build(v * 2 + 1, mid + 1, tr);
  19.     t[v] = merge(t[v * 2], t[v * 2 + 1]);
  20. }
  21. void push(int v, int tl, int tr) {
  22.     if (upd[v] == inf)return;
  23.     t[v] = //???
  24.     if (tl != tr)upd[v] -> upd[v * 2], upd[v] -> upd[v * 2 + 1];
  25.     upd[v] = inf;
  26. }
  27. void update(int v, int tl, int tr, int l, int r, int x) {
  28.     push(v, tl, tr);
  29.     if (tr < l || tl > r)return;
  30.     if (tl >= l && tr <= r) {
  31.         x -> upd[v];
  32.         push(v, tl, tr);
  33.         return;
  34.     }
  35.     int mid = (tl + tr) / 2;
  36.     update(v * 2, tl, mid, l, r, x), update(v * 2 + 1, mid + 1, tr, l, r, x);
  37.     t[v] = merge(t[v * 2], t[v * 2 + 1]);
  38. }
  39. node get(int v, int tl, int tr, int pos) {
  40.     push(v, tl, tr);
  41.     if (tl == tr)return t[v];
  42.     int mid = (tl + tr) / 2;
  43.     if (pos <= mid)return get(v * 2, tl, mid, pos);
  44.     return get(v * 2 + 1, mid + 1, tr, pos);
  45. }
Tags: segment tree
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement