#include<bits/stdc++.h>
#include "wall.h"
using namespace std;
const int INF=1987654321;
struct A{
int st, en;
A operator+(const A &r){
int x=max(r.st, st), y=min(r.en, en);
if(x<=y) return (A){x, y};
else if(x==r.st) return (A){x, x};
else return (A){y, y};
}
}tree[10000010];
int n, m;
void make_tree(int node, int s, int e){
if(s==e){
tree[node]=(A){0, INF};
return;
}
int m=s+e>>1;
make_tree(node*2, s, m);
make_tree(node*2+1, m+1, e);
tree[node]=tree[node*2]+tree[node*2+1];
}
void update(int node, int s, int e, int s1, int e1, A val){
if(s>e1||e<s1) return;
if(s1<=s&&e<=e1){
tree[node]=tree[node]+val;
return;
}
if(tree[node].st!=0||tree[node].en!=INF){
tree[node*2]=tree[node*2]+tree[node];
tree[node*2+1]=tree[node*2+1]+tree[node];
tree[node]=(A){0, INF};
}
int m=s+e>>1;
update(node*2, s, m, s1, e1, val);
update(node*2+1, m+1, e, s1, e1, val);
}
A get(int node, int s, int e, int pos){
if(s>pos||e<pos) return (A){0, INF};
if(s==e){
return tree[node];
}
if(tree[node].st!=0||tree[node].en!=INF){
tree[node*2]=tree[node*2]+tree[node];
tree[node*2+1]=tree[node*2+1]+tree[node];
tree[node]=(A){0, INF};
}
int m=s+e>>1;
return get(node*2, s, m, pos)+get(node*2+1, m+1, e, pos);
}
void buildWall(int N, int M, int op[], int left[], int right[], int height[], int finalHeight[]){
n=N, m=M;
make_tree(1, 0, n-1);
for(int i=0; i<m; i++){
int type=op[i], s=left[i], e=right[i], x=height[i];
if(type==1){
A rev=(A){x, INF};
update(1, 0, n-1, s, e, rev);
}
else{
A rev=(A){0, x};
update(1, 0, n-1, s, e, rev);
}
}
for(int i=0; i<n; i++) finalHeight[i]=get(1, 0, n-1, i).st;
}
