#include <stdlib.h>
#include <algorithm>
using namespace std;
static int N,K,*H;
struct NODE{
NODE(int h=0): mini(h),maxi(h),left(NULL),right(NULL) {}
int mini,maxi;
NODE *left,*right;
};
void dfs(NODE *now,int s,int e,int l,int r,int mini,int maxi,int op,int h)
{
if (mini <= now->mini && now->maxi <= maxi);
else if (now->mini < mini && maxi < now->maxi) now->mini = mini, now->maxi = maxi;
else if (maxi < now->mini) now->mini = now->maxi = maxi;
else if (now->maxi < mini) now->mini = now->maxi = mini;
else if (mini > now->mini) now->mini = mini;
else if (maxi < now->maxi) now->maxi = maxi;
mini = now->mini; maxi = now->maxi;
if (e < l || s > r) return;
if (l <= s && e <= r){
if (op == 1){ // add
if (now->mini < h) now->mini = h;
if (now->maxi < h) now->maxi = h;
}else{ // remove
if (now->maxi > h) now->maxi = h;
if (now->mini > h) now->mini = h;
}
return;
}
int m = (s+e)>>1;
if (now->left == NULL){
now->left = new NODE(now->mini);
now->right = new NODE(now->mini);
}
dfs(now->left,s,m,l,r,mini,maxi,op,h);
dfs(now->right,m+1,e,l,r,mini,maxi,op,h);
now->mini = min(now->left->mini,now->right->mini);
now->maxi = max(now->left->maxi,now->right->maxi);
}
void cdfs(NODE *now,int s,int e,int mini,int maxi)
{
if (mini <= now->mini && now->maxi <= maxi);
else if (now->mini < mini && maxi < now->maxi) now->mini = mini, now->maxi = maxi;
else if (maxi < now->mini) now->mini = now->maxi = maxi;
else if (now->maxi < mini) now->mini = now->maxi = mini;
else if (mini > now->mini) now->mini = mini;
else if (maxi < now->maxi) now->maxi = maxi;
mini = now->mini; maxi = now->maxi;
if (mini == maxi){
for (int i=s;i<=e;i++) H[i] = mini;
return;
}
int m = (s+e)>>1;
cdfs(now->left,s,m,mini,maxi);
cdfs(now->right,m+1,e,mini,maxi);
}
void buildWall(int n,int k,int op[],int left[],int right[],int height[],int finalHeight[])
{
int i;
NODE *root = new NODE();
N = n, K = k;
for (i=0;i<K;i++){
dfs(root,0,N-1,left[i],right[i],0,1e9,op[i],height[i]);
}
H = finalHeight;
cdfs(root,0,N-1,0,1e9);
}
