#include "wall.h"
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e6+10;
const int inf = 1e9+10;
#define pb push_back
#define mp make_pair
#define fr first
#define sc second
#define all(x) x.begin(),x.end()
int n, a[maxn], trmn1[4*maxn],trmn2[4*maxn],trmx1[4*maxn],trmx2[4*maxn], lzadd[4*maxn], lzrem[4*maxn];
void build(int no, int l, int r) {
lzadd[no] = lzrem[no] = -1;
if(l == r) {
trmn1[no] = trmn2[no] = trmx1[no] = trmx2[no] = a[l]; return;
}
int f1=2*no,f2=2*no+1,mid=(l+r)>>1;
build(f1,l,mid);
build(f2,mid+1,r);
trmn1[no] = min(trmn1[f1],trmn1[f2]);
trmn2[no] = min(trmn2[f1],trmn2[f2]);
if(trmn1[no] != trmn1[f1]) trmn2[no] = min(trmn2[no],trmn1[f1]);
if(trmn1[no] != trmn1[f2]) trmn2[no] = min(trmn2[no],trmn1[f2]);
}
void flush(int no, int l, int r) {
if(lzadd[no] != -1) {
trmn1[no] = max(trmn1[no],lzadd[no]);
trmn2[no] = max(trmn2[no],lzadd[no]);
trmx1[no] = max(trmx1[no],lzadd[no]);
trmx2[no] = max(trmx2[no],lzadd[no]);
if(l != r) {
int f1=2*no,f2=2*no+1,mid=(l+r)>>1;
if(lzadd[f1] == -1) lzadd[f1] = lzadd[no];
else lzadd[f1] = max(lzadd[f1],lzadd[no]);
if(lzadd[f2] == -1) lzadd[f2] = lzadd[no];
else lzadd[f2] = max(lzadd[f2],lzadd[no]);
}
lzadd[no] = -1;
}
if(lzrem[no] != -1) {
trmn1[no] = min(trmn1[no],lzadd[no]);
trmn2[no] = min(trmn2[no],lzadd[no]);
trmx1[no] = min(trmx1[no],lzadd[no]);
trmx2[no] = min(trmx2[no],lzadd[no]);
if(l != r) {
int f1=2*no,f2=2*no+1,mid=(l+r)>>1;
if(lzrem[f1] == -1) lzrem[f1] = lzrem[no];
else lzrem[f1] = min(lzrem[f1],lzrem[no]);
if(lzrem[f2] == -1) lzrem[f2] = lzrem[no];
else lzrem[f2] = min(lzrem[f2],lzrem[no]);
}
lzrem[no] = -1;
}
}
//a[i] = max(a[i],val)
void attadd(int no, int l, int r, int L, int R, int val) {
flush(no,l,r);
if(l > R || r < L) return;
if(l >= L && r <= R) {
trmx1[no] = max(trmx1[no],val);
trmx2[no] = max(trmx2[no],val);
if(l == r) {
trmn1[no] = max(trmn1[no],val);
trmn2[no] = max(trmn1[no],val);
return;
}
if(trmn1[no] >= val) return;
if(trmn2[no] > val) {
lzadd[no] = val;
flush(no,l,r);
return;
}
}
int f1=2*no,f2=2*no+1,mid=(l+r)>>1;
attadd(f1,l,mid,L,R,val);
attadd(f2,mid+1,r,L,R,val);
trmn1[no] = min(trmn1[f1],trmn1[f2]);
trmn2[no] = min(trmn2[f1],trmn2[f2]);
if(trmn1[no] != trmn1[f1]) trmn2[no] = min(trmn2[no],trmn1[f1]);
if(trmn1[no] != trmn1[f2]) trmn2[no] = min(trmn2[no],trmn1[f2]);
trmx1[no] = max(trmx1[f1],trmx1[f2]);
trmx2[no] = max(trmx2[f1],trmx2[f2]);
if(trmx1[no] != trmx1[f1]) trmx2[no] = max(trmx2[no],trmx1[f1]);
if(trmx1[no] != trmx1[f2]) trmx2[no] = max(trmx2[no],trmx1[f2]);
}
void attrem(int no, int l, int r, int L, int R, int val) {
flush(no,l,r);
if(l > R || r < L) return;
if(l >= L && r <= R) {
trmn1[no] = min(trmn1[no],val);
trmn2[no] = min(trmn2[no],val);
if(l == r) {
trmx1[no] = min(trmx1[no],val);
trmx2[no] = min(trmx1[no],val);
return;
}
if(trmx1[no] <= val) return;
if(trmx2[no] < val) {
lzrem[no] = val;
flush(no,l,r);
return;
}
}
int f1=2*no,f2=2*no+1,mid=(l+r)>>1;
attrem(f1,l,mid,L,R,val);
attrem(f2,mid+1,r,L,R,val);
trmx1[no] = max(trmx1[f1],trmx1[f2]);
trmx2[no] = max(trmx2[f1],trmx2[f2]);
if(trmx1[no] != trmx1[f1]) trmx2[no] = max(trmx2[no],trmx1[f1]);
if(trmx1[no] != trmx1[f2]) trmx2[no] = max(trmx2[no],trmx1[f2]);
trmn1[no] = min(trmn1[f1],trmn1[f2]);
trmn2[no] = min(trmn2[f1],trmn2[f2]);
if(trmn1[no] != trmn1[f1]) trmn2[no] = min(trmn2[no],trmn1[f1]);
if(trmn1[no] != trmn1[f2]) trmn2[no] = min(trmn2[no],trmn1[f2]);
}
void findans(int no, int l, int r) {
flush(no,l,r);
if(l == r) {
a[l] = trmx1[no];
return;
}
int f1=2*no,f2=2*no+1,mid=(l+r)>>1;
findans(f1,l,mid);
findans(f2,mid+1,r);
}
void buildWall(int N, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
n = N;
build(1,0,n-1);
for(int i = 0; i < k; i++) {
if(op[i] == 1) attadd(1,0,n-1,left[i],right[i],height[i]);
if(op[i] == 2) attrem(1,0,n-1,left[i],right[i],height[i]);
}
findans(1,0,n-1);
for(int i = 0; i < n; i++) {
finalHeight[i] = a[i];
}
}
