#include <bits/stdc++.h>
//#include "wall.h"
#define MAX_N 2000000
using namespace std;
const int MAX = 100000;
const int MIN = 0;
int rez[MAX_N + 1];
struct aint
{
int st, dr;
};
aint arb[(MAX_N << 2) + 1];
void upd(int poz, int st, int dr, int a, int b, int x, int y)
{
//cout << "FACEM UPD " << poz << " " << st << " " << dr << " " << " INterv " << a << " " << b << " BVAL " << x << " " << y << "\n";
if(st == a && dr == b)
{
if(x > arb[poz].dr)
{
arb[poz] = {x, x};
}
else
if(y < arb[poz].st)
arb[poz] = {y, y};
else
{
arb[poz].st = max(arb[poz].st, x);
arb[poz].dr = min(arb[poz].dr, y);
}
return;
}
int mid = (st + dr) >> 1;
upd(poz << 1, st, mid, st, mid, arb[poz].st, arb[poz].dr);
upd((poz << 1) + 1, mid + 1, dr, mid + 1, dr, arb[poz].st, arb[poz].dr);
arb[poz] = {MIN, MAX};
if(b <= mid)
upd(poz << 1, st, mid, a, b, x, y);
if(a > mid)
upd((poz << 1) + 1, mid + 1, dr, a, b, x, y);
if(a <= mid && b > mid)
{
upd(poz << 1, st, mid, a, mid, x, y);
upd((poz << 1) + 1, mid + 1, dr, mid + 1, b, x, y);
}
}
void build(int poz, int st, int dr)
{
arb[poz] = {MIN, MAX};
if(st == dr)
return;
int mid = (st + dr) >> 1;
build(poz << 1, st, mid);
build((poz << 1) + 1, mid + 1, dr);
}
void dfs(int poz, int st, int dr)
{
if(st == dr)
{
rez[st] = arb[poz].st;
return;
}
int mid = (st + dr) >> 1;
upd(poz << 1, st, mid, st, mid, arb[poz].st, arb[poz].dr);
upd((poz << 1) + 1, mid + 1, dr, mid + 1, dr, arb[poz].st, arb[poz].dr);
arb[poz] = {MIN, MAX};
dfs(poz << 1, st, mid);
dfs((poz << 1) + 1, mid + 1, dr);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
build(1, 1, n);
for(int i = 0; i < k; i ++)
{
int st = left[i] + 1;
int dr = right[i] + 1;
int nr = height[i];
if(op[i] == 2)
upd(1, 1, n, st, dr, MIN, nr);
else
upd(1, 1, n, st, dr, nr, MAX);
}
dfs(1, 1, n);
for(int i = 0; i < n; i ++)
finalHeight[i] = rez[i + 1];
}
