/**
* One of the most interesting problems in the year! I began by investigating two
* consecutive phases. We have:
* (1) add(u) + add(v) is equivalent to add(max(u,v));
* (2) remove(u) + remove(v) is equivalent to remove(min(u,v));
* (3) add(u) + remove(v) (where u > v) changes all values to v;
* (4) add(u) + remove(v) (where u <= v) increases values <u to u, decreases values
* >v to v, and keeps values in [u,v] unchanged;
* (5) remove(v) + add(u) (where u <= v) does the same as (4).
* In particular, (4) & (5) aroused my interest. Indeed, when we picture a set of
* points placed on the real number line at 0,1,2,...,T, we see that after applying
* the k operations to all points, the resultant points still form a contigous
* range.
*
* Now, I'll formally describe my solution. Let an "active range" [a,b] be an
* operation which:
* increases values <a to a, decreases values >b to b, and keeps the
* remaining values unchanged.
* We now claim that the combination of a few phases is equivalent to an active
* range. For example, add(3) + remove(4) => [3,4], while add(3) + remove(2)
* + add(4) => [4,4] (case (3), (4)).
* First, add(val) => [val,INF] and remove(val) => [-INF,val]. (This is (1) & (2).)
* With some case work, we can then check that the combination of two active range
* is another active range. (Quite intuitive, I suppose?)
*
* This means that we can maintain a segment tree with nodes which are "active
* ranges". Its underlying array should have q active ranges, each one representing
* a phase. By default, all of the q underlying nodes are "inactive" (set to
* [-INF,INF]). We'll turn them active by setting one of the underlying range to the
* one corresponding to the actual phase. We then traverse from 0 to n-1, each time
* computing finalHeight[i] with the overall active range (at the root of the tree).
* As each phase operates on a contigous range, we have to modify the seg tree by
* O(k) times. Nice problem~
*
* Time Complexity: O(n + k * log(k)) (Full solution)
* Implementation 1 (Offline algorithm, Segment Tree)
*/
#include <bits/stdc++.h>
#include "wall.h"
typedef std::vector<int> vec;
int H_MAX = 1e5;
// A type 1 segment tree
template<class T> struct SegTree {
int n;
std::vector<T> tree;
SegTree(int _n, const T& identity) {
n = _n;
tree.assign(4 * n, identity);
}
void _update(int pos, const T& val, int k, int i, int j) {
if (i == j) {
tree[k] = val;
return;
}
int mid = (i + j) / 2;
if (pos <= mid)
_update(pos, val, 2 * k, i, mid);
else
_update(pos, val, 2 * k + 1, mid + 1, j);
tree[k] = merge(tree[2 * k], tree[2 * k + 1]);
}
inline void update(int pos, const T& val) { _update(pos, val, 1, 0, n - 1); }
};
struct range_t {
int l, r;
};
const range_t ID = {0, H_MAX};
range_t merge(const range_t& r1, const range_t& r2) {
assert(r1.l <= r1.r && r2.l <= r2.r);
if (r1.r <= r2.l)
return range_t{r2.l, r2.l};
else if (r2.r <= r1.l)
return range_t{r2.r, r2.r};
else
return range_t{std::max(r1.l, r2.l), std::min(r1.r, r2.r)};
}
void buildWall(int n, int q, int op[], int l[], int r[], int h[], int ans[]) {
std::vector<vec> add(n + 1), remove(n + 1);
for (int i = 0; i < q; i++) {
add[l[i]].push_back(i);
remove[r[i] + 1].push_back(i);
}
SegTree<range_t> tree(q, ID); // all default to inactive
for (int i = 0; i < n; i++) {
for (int qi : add[i]) {
if (op[qi] == 1)
tree.update(qi, range_t{h[qi], H_MAX});
else
tree.update(qi, range_t{0, h[qi]});
}
for (int qi : remove[i])
tree.update(qi, ID);
ans[i] = tree.tree[1].l;
}
}
