#include <iostream>
#include "wall.h"
using namespace std;
const int Nn = (1<<21) + 1;
int Mx[Nn<<1], Mn[Nn<<1], inf = 1e9;
void update(int cur, int tp, int h){
if (tp == 1){
Mx[cur] = max(Mx[cur], h);
Mn[cur] = max(Mn[cur], h);
}
else{
Mn[cur] = min(Mn[cur], h);
Mx[cur] = min(Mx[cur], h);
}
}
void update(int tp, int l, int r, int h, int cur = 1, int st = 1, int en = Nn){
if (l >= en or r <= st)
return;
if (l <= st and r >= en){
update(cur, tp, h);
return;
}
int lc = cur + cur, rc = lc + 1, mid = (st + en) / 2;
update(lc, 1, Mx[cur]);
update(lc, 2, Mn[cur]);
update(rc, 1, Mx[cur]);
update(rc, 2, Mn[cur]);
update(tp, l, r, h, lc, st, mid);
update(tp, l, r, h, rc, mid, en);
Mx[cur] = min(Mx[lc], Mx[rc]);
Mn[cur] = max(Mn[lc], Mn[rc]);
}
int get(int i, int cur = 1, int st = 1, int en = Nn){
if (i >= en or i < st)
return 0;
if (en - st == 1)
return max(0, Mx[cur]);
int lc = cur + cur, rc = lc + 1, mid = (st + en) / 2;
update(lc, 1, Mx[cur]);
update(lc, 2, Mn[cur]);
update(rc, 1, Mx[cur]);
update(rc, 2, Mn[cur]);
return get(i, lc, st, mid) + get(i, rc, mid, en);
}
void buildWall(int n, int k, int op[], int lft[], int rgt[], int ht[], int ans[]){
for (int i=0;i<k;i++)
update(op[i], lft[i] + 1, rgt[i] + 2, ht[i]);
for (int i=1;i<=n;i++)
ans[i-1] = get(i);
}
