#include "wall.h"
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <utility>
using namespace std;
typedef pair<int, int> ii;
enum state {
BUILD, DESTROY
};
struct node {
int i, j;
node *left, *right;
int max_height, min_height;
int lazy_u, lazy_d;
void combine(int h, state op) {
if (h == -1) return;
if (op == BUILD) {
this->lazy_u = max(this->lazy_u, h);
if (h > this->lazy_d && this->lazy_d != -1) {
this->lazy_d = h;
}
} else if (op == DESTROY) {
if (this->lazy_d == -1) {
this->lazy_d = h;
} else {
this->lazy_d = min(this->lazy_d, h);
}
if (h < this->lazy_u) {
this->lazy_u = h;
}
}
}
};
node *build(int i, int j) {
if (i == j) {
return new node{i, j, NULL, NULL, 0, 0, -1, -1};
}
node *left = build(i, (i + j) / 2);
node *right = build((i + j) / 2 + 1, j);
return new node{i, j, left, right, 0, 0, -1, -1};
}
void propagate(node *cur) {
/* update current node */
if (cur->lazy_u != -1) {
cur->max_height = max(cur->max_height, cur->lazy_u);
cur->min_height = max(cur->min_height, cur->lazy_u);
}
if (cur->lazy_d != -1) {
cur->min_height = min(cur->min_height, cur->lazy_d);
cur->max_height = min(cur->max_height, cur->lazy_d);
}
/* update child */
if (cur->left != NULL) {
cur->left->combine(cur->lazy_u,BUILD);
cur->left->combine(cur->lazy_d,DESTROY);
cur->right->combine(cur->lazy_u,BUILD);
cur->right->combine(cur->lazy_d,DESTROY);
}
cur->lazy_d = cur->lazy_u = -1;
}
int query(node *cur, int i) {
propagate(cur);
if (cur->j < i || cur->i > i) return 0;
if (cur->i == i && cur->j == i) {
return cur->max_height;
}
return query(cur->left, i) + query(cur->right, i);
}
void update(state op, int i, int j, int h, node *cur) {
propagate(cur);
if (cur->j < i || cur->i > j) {
return;
}
if (cur->i >= i && cur->j <= j) {
cur->combine(h, op);
return;
}
update(op, i, j, h, cur->left);
update(op, i, j, h, cur->right);
if (op == BUILD) {
cur->max_height = max(cur->max_height, h);
cur->min_height = max(cur->min_height, h);
}
if (op == DESTROY) {
cur->max_height = min(cur->max_height, h);
cur->min_height = min(cur->min_height, h);
}
return;
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
node *root = build(0, n - 1);
for (int i = 0 ; i < k; i++) {
if (op[i] == 1) {
update(BUILD, left[i], right[i], height[i], root);
} else if (op[i] == 2) {
update(DESTROY, left[i], right[i], height[i], root);
}
}
for (int i = 0; i < n; i++) {
finalHeight[i] = query(root, i);
}
return;
}
/*int main() {
int n, k;
scanf("%d %d", &n, &k);
//int op[5], left[5], right[5], height[5];
int *op, *left, *right, *height;
op = (int *) malloc (sizeof (int) * 500005);
left = (int *) malloc (sizeof (int) * 500005);
right = (int *) malloc (sizeof (int) * 500005);
height = (int *) malloc (sizeof (int) * 500005);
//int op[500005], left[500005], right[500005], height[500005];
for (int i = 0; i < k; i++) {
scanf("%d %d %d %d",op+i,&left[i], &right[i], &height[i]);
}
int *finalHeight = (int *) malloc (sizeof (int) * 2000005);
buildWall(n, k, op, left, right, height, finalHeight);
for (int i = 0; i < n; i++) {
printf("%d\n", finalHeight[i]);
}
return 0;
}*/
