Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- struct node {
- int x, y, z;//можно называть любым способом
- };
- node t[4 * N], upd[4 * N];
- node merge(node a, node b) {
- node res;
- res.x = //???
- res.y = //???
- res.z = //??? зависит от задачи
- return res;
- }
- void build(int v, int tl, int tr) {
- if (tl == tr) {
- t[v] = {?, ?, ?};
- return;
- }
- int mid = (tl + tr) / 2;
- build(v * 2, tl, mid), build(v * 2 + 1, mid + 1, tr);
- t[v] = merge(t[v * 2], t[v * 2 + 1]);
- }
- void push(int v, int tl, int tr) {
- if (upd[v] == inf)return;
- t[v] = //???
- if (tl != tr)upd[v] -> upd[v * 2], upd[v] -> upd[v * 2 + 1];
- upd[v] = inf;
- }
- void update(int v, int tl, int tr, int l, int r, int x) {
- push(v, tl, tr);
- if (tr < l || tl > r)return;
- if (tl >= l && tr <= r) {
- x -> upd[v];
- push(v, tl, tr);
- return;
- }
- int mid = (tl + tr) / 2;
- update(v * 2, tl, mid, l, r, x), update(v * 2 + 1, mid + 1, tr, l, r, x);
- t[v] = merge(t[v * 2], t[v * 2 + 1]);
- }
- node get(int v, int tl, int tr, int pos) {
- push(v, tl, tr);
- if (tl == tr)return t[v];
- int mid = (tl + tr) / 2;
- if (pos <= mid)return get(v * 2, tl, mid, pos);
- return get(v * 2 + 1, mid + 1, tr, pos);
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement