#include "wall.h" #include <bits/stdc++.h> using namespace std; // #define cerr if (false) cerr const int OO = (int)1e18; struct Segtree { int height = 0; int numleaves; vector<int> nL, nR; // lo: build // hi: cut vector<int> lo, hi; Segtree (int n) { numleaves = 1; while (numleaves < n) numleaves *= 2, height++; lo.assign(2*numleaves, 0); hi.assign(2*numleaves, 0); nL.assign(2*numleaves, 0); nR.assign(2*numleaves, 0); for (int i = 0; i < numleaves; i++) { nL[i + numleaves] = i, nR[i + numleaves] = i; } for (int i = numleaves-1; i > 0; i--) { nL[i] = nL[2*i], nR[i] = nR[2*i+1]; } } 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 < (int)lo.size()) { pair<int,int> leftPair = combine(pair<int,int>{lo[node], hi[node]}, pair<int,int>{lo[2*node], hi[2*node]}); lo[2*node] = leftPair.first; hi[2*node] = leftPair.second; pair<int,int> rightPair = combine(pair<int,int>{lo[node], hi[node]}, pair<int,int>{lo[2*node+1], hi[2*node+1]}); lo[2*node+1] = rightPair.first; hi[2*node+1] = rightPair.second; } } int get (int idx) { int node = 1; while (node < numleaves) { pushdown(node); if (nL[2*node] <= idx && idx <= nR[2*node]) { node = 2*node; } else { node = 2*node+1; } } return lo[node]; } void update (int node, int qL, int qR, int newLo, int newHi) { pushdown(node); if (qL <= nL[node] && nR[node] <= qR) { pair<int,int> inter = combine(pair<int,int>{newLo, newHi}, pair<int,int>{lo[node], hi[node]}); lo[node] = inter.first; hi[node] = inter.second; pushdown(node); } else if (nR[node] < qL || qR < nL[node]) { return; } else { update(2*node, qL, qR, newLo, newHi); update(2*node+1, qL, qR, newLo, newHi); lo[node] = min(lo[2*node], lo[2*node+1]); hi[node] = max(hi[2*node], hi[2*node+1]); } } void dbg () { // cerr << "Wall:\n"; // for (int i = 0; i < numleaves; i++) cerr << get(i) << " "; // cerr << "\n"; cerr << "Tree:\n"; for (int h = 0; h <= height; h++) { for (int i = (1 << h); i < (1 << (h+1)); i++) { cerr << "(" << lo[i] << ", " << hi[i] << ") "; } cerr << "\n"; } cerr << "\n"; } }; 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(1, leftQ[q], rightQ[q], heightQ[q], OO); } else { // cut wall.update(1, leftQ[q], rightQ[q], 0, heightQ[q]); } // wall.dbg(); } for (int i = 0; i < N; i++) { finalHeight[i] = wall.get(i); } }