#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math,inline")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,lzcnt,mmx,abm,avx,avx2,fma")
#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 2e6, inf = INT_MAX;
struct node {
int mx, mn;
};
int n, lazMx[N*4], lazMn[N*4];
node seg[N*4];
void build(int p=1, int l=0, int r=n-1) {
if (l == r) {
seg[p].mx = 0;
seg[p].mn = 0;
return;
}
int mid = (l+r) >> 1;
seg[p].mx = seg[p].mn = 0;
}
void updateMx(int a, int b, int c, int p=1, int l=0, int r=n-1) {
if (seg[p].mn >= c) return;
else if (l == r) {
seg[p].mx = max(seg[p].mx, c);
seg[p].mn = max(seg[p].mn, c);
return;
}
int mid = (l+r) >> 1;
if (a <= mid) updateMx(a, b, c, p*2, l, mid);
if (mid+1 <= b) updateMx(a, b, c, p*2+1, mid+1, r);
seg[p].mx = max(seg[p*2].mx, seg[p*2+1].mx);
seg[p].mn = min(seg[p*2].mn, seg[p*2+1].mn);
}
void updateMn(int a, int b, int c, int p=1, int l=0, int r=n-1) {
if (seg[p].mx <= c) return;
else if (l == r) {
seg[p].mx = min(seg[p].mx, c);
seg[p].mn = min(seg[p].mn, c);
return;
}
int mid = (l+r) >> 1;
if (a <= mid) updateMn(a, b, c, p*2, l, mid);
if (mid+1 <= b) updateMn(a, b, c, p*2+1, mid+1, r);
seg[p].mx = max(seg[p*2].mx, seg[p*2+1].mx);
seg[p].mn = min(seg[p*2].mn, seg[p*2+1].mn);
}
int query(int a, int p=1, int l=0, int r=n-1) {
if (l == r) {
return seg[p].mx;
}
//pushDown(p);
int mid = (l+r) >> 1;
if (a <= mid) return query(a, p*2, l, mid);
else return query(a, p*2+1, mid+1, r);
}
void buildWall(int NN, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
n = NN;
build();
for (int i = 0; i < k; i++) {
if (op[i] == 1) updateMx(left[i], right[i], height[i]);
else updateMn(left[i], right[i], height[i]);
}
for (int i = 0; i < n; i++) {
finalHeight[i] = query(i);
}
}
