#include "wall.h" #include <bits/stdc++.h> using namespace std; // #define cerr if (false) cerr const int OO = (int)1e18; struct Segtree { int numleaves; // lo: build // hi: cut vector<pair<int,int>> tree; Segtree (int n) { numleaves = 1; while (numleaves < n) numleaves *= 2; tree.assign(2*numleaves, pair<int,int>{0, 0}); } pair<int,int> combine(pair<int,int> newInter, pair<int,int> oldInter) { if (newInter.first > oldInter.second) { return pair<int,int>{newInter.first, newInter.first}; } else if (oldInter.first > newInter.second) { return pair<int,int>{newInter.second, newInter.second}; } else { return pair<int,int>{max(newInter.first, oldInter.first), min(newInter.second, oldInter.second)}; } } void pushdown (int node) { if (2*node+1 < 2*numleaves) { tree[2*node] = combine(tree[node], tree[2*node]); tree[2*node+1] = combine(tree[node], tree[2*node+1]); } } int get (int node, int nL, int nR, int target) { pushdown(node); if (node >= numleaves) { return tree[node].first; } else { int nMid = nL + (nR - nL) / 2; if (nL <= target && target <= nMid) { return get(2*node, nL, nMid, target); } else { return get(2*node+1, nMid+1, nR, target); } } } int get (int target) { return get(1, 0, numleaves-1, target); } void update (int node, int nL, int nR, int qL, int qR, pair<int,int> newInter) { pushdown(node); if (qL <= nL && nR <= qR) { tree[node] = combine(newInter, tree[node]); pushdown(node); } else if (nR < qL || qR < nL) { return; } else { int nMid = nL + (nR - nL) / 2; update(2*node, nL, nMid, qL, qR, newInter); update(2*node+1, nMid+1, nR, qL, qR, newInter); tree[node] = pair<int,int>{min(tree[2*node].first, tree[2*node+1].first), max(tree[2*node].second, tree[2*node+1].second)}; } } void update (int qL, int qR, pair<int,int> newInter) { update(1, 0, numleaves-1, qL, qR, newInter); } }; void buildWall(int N, int Q, int typeQ[], int leftQ[], int rightQ[], int heightQ[], int finalHeight[]){ Segtree wall(N); for (int q = 0; q < Q; q++) { if (typeQ[q] == 1) { // build wall.update(leftQ[q], rightQ[q], pair<int,int>{heightQ[q], OO}); } else { // cut wall.update(leftQ[q], rightQ[q], pair<int,int>{0, heightQ[q]}); } } for (int i = 0; i < N; i++) { finalHeight[i] = wall.get(i); } }