#include <bits/stdc++.h>
#include "wall.h"
using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 1 << 17;
int add[N << 2], del[N << 2];
void push(int i, int l, int r){
if(l != r){
add[i << 1] = max(add[i << 1], add[i]);
add[i << 1] = min(add[i << 1], del[i]);
del[i << 1] = max(del[i << 1], add[i]);
del[i << 1] = min(del[i << 1], del[i]);
add[i << 1 | 1] = max(add[i << 1 | 1], add[i]);
add[i << 1 | 1] = min(add[i << 1 | 1], del[i]);
del[i << 1 | 1] = max(del[i << 1 | 1], add[i]);
del[i << 1 | 1] = min(del[i << 1 | 1], del[i]);
add[i] = 0, del[i] = INF;
}
}
void updAdd(int l, int r, int i, int from, int to, int val){
push(i, from, to);
if (from > r || to < l)
return;
if (from >= l && to <= r)
{
add[i] = max(add[i], val);
del[i] = max(del[i], val);
push(i, from, to);
return;
}
int mid = (from + to) >> 1;
updAdd(l, r, i << 1, from, mid, val);
updAdd(l, r, i << 1 | 1, mid + 1, to, val);
}
void updDel(int l, int r, int i, int from, int to, int val){
push(i, from, to);
if(from > r || to < l) return;
if(from >= l && to <= r){
add[i] = min(add[i], val);
del[i] = min(del[i], val);
push(i, from, to);
return;
}
int mid = (from + to) >> 1;
updDel(l, r, i << 1, from, mid, val);
updDel(l, r, i << 1 | 1, mid + 1, to , val);
}
void pushall(int i, int l, int r){
if(l == r) return;
push(i, l, r);
int mid = (l + r) >> 1;
pushall(i << 1, l, mid);
pushall(i << 1 | 1, mid + 1, r);
}
void buildWall(int n, int k, int op[], int l[], int r[], int h[], int ans[]){
memset(del, INF, sizeof del);
for(int i = 0; i < k; i++){
if(op[i] == 1){
updAdd(l[i], r[i], 1, 0, N - 1, h[i]);
}
else{
updDel(l[i], r[i], 1, 0, N - 1, h[i]);
}
}
pushall(1, 0, N - 1);
for(int i = 0; i < n; i++){
ans[i] = min(add[i + N], del[i + N]);
}
}
