#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define INF 1e9
struct Node {
int mn, mx;
Node() {
mn = 0, mx = INF;
}
};
int N, K;
Node tree[8000005];
Node lazy[8000005];
bool hasLazy[8000005];
Node intersect(Node &a, Node &b) { // (prev_node, update_node)
Node ans = Node();
if (a.mx < b.mn) {
ans.mn = b.mn;
ans.mx = b.mn;
} else if (a.mn > b.mx) {
ans.mn = b.mx;
ans.mx = b.mx;
} else {
ans.mn = max(a.mn, b.mn);
ans.mx = min(a.mx, b.mx);
}
return ans;
}
void push(int idx, int l, int r) {
if (!hasLazy[idx]) return;
tree[idx] = intersect(tree[idx], lazy[idx]);
if (l != r) {
lazy[idx*2] = intersect(lazy[idx*2], lazy[idx]);
lazy[idx*2+1] = intersect(lazy[idx*2+1], lazy[idx]);
hasLazy[2*idx] = hasLazy[2*idx+1] = 1;
}
lazy[idx] = Node();
hasLazy[idx] = 0;
}
void updateLower(int idx, int l, int r, int ql, int qr, int val) {
if (r < ql || l > qr) return;
if (ql <= l && r <= qr) {
Node A = Node();
A.mn = val;
lazy[idx] = intersect(lazy[idx], A);
hasLazy[idx] = 1;
push(idx, l, r);
return;
}
if (l != r) {
push(idx, l, r);
int mid = (l + r) >> 1;
updateLower(2*idx, l, mid, ql, qr, val);
updateLower(2*idx+1, mid + 1, r, ql, qr, val);
}
}
void updateUpper(int idx, int l, int r, int ql, int qr, int val) {
if (r < ql || l > qr) return;
if (ql <= l && r <= qr) {
Node A = Node();
A.mx = val;
lazy[idx] = intersect(lazy[idx], A);
hasLazy[idx] = 1;
push(idx, l, r);
return;
}
if (l != r) {
push(idx, l, r);
int mid = (l + r) >> 1;
updateUpper(2*idx, l, mid, ql, qr, val);
updateUpper(2*idx+1, mid + 1, r, ql, qr, val);
}
}
int query(int idx, int l, int r, int k) {
push(idx, l, r);
if (l == r) {
return tree[idx].mn;
}
int mid = (l + r) >> 1;
if (k <= mid) {
return query(idx*2, l, mid, k);
} else {
return query(idx*2 + 1, mid + 1, r, k);
}
return 0;
}
void print_tree(int idx, int l, int r) {
cout << "[" << l << "," << r << "] : " << tree[idx].mn << " " << tree[idx].mx << endl;
if (l != r) {
int mid = (l + r) >> 1;
print_tree(2*idx, l, mid);
print_tree(2*idx+1, mid + 1, r);
}
}
void print_lazy(int idx, int l, int r) {
cout << "[" << l << "," << r << "] : " << lazy[idx].mn << " " << lazy[idx].mx << endl;
if (l != r) {
int mid = (l + r) >> 1;
print_lazy(2*idx, l, mid);
print_lazy(2*idx+1, mid + 1, r);
}
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
N = n, K = k;
for (int i = 0; i < k; i++) {
if (op[i] == 1) {
updateLower(1, 0, N - 1, left[i], right[i], height[i]);
} else {
updateUpper(1, 0, N - 1, left[i], right[i], height[i]);
}
}
/*
print_tree(1, 0, N - 1);
cout << "\n--------\n";
print_lazy(1, 0, N - 1);
cout << "\n--------\n";
*/
for (int i = 0; i < N; i++) {
finalHeight[i] = query(1, 0, N - 1, i);
}
}
