// GPT's code
#include <bits/stdc++.h>
#include "wall.h"
using namespace std;
struct Node {
int mn, mx; // min/max in the segment
int mn2, mx2; // second min/max
int cnt_mn, cnt_mx; // count of min/max
int lazy; // lazy for assignment, -1 means no assignment
};
const int N = 200000 + 5;
Node seg[4*N];
int n;
void push_up(int idx) {
Node &L = seg[idx*2], &R = seg[idx*2+1], &cur = seg[idx];
cur.mn = min(L.mn, R.mn);
cur.mx = max(L.mx, R.mx);
// second min
vector<int> tmp;
if (L.mn != cur.mn) tmp.push_back(L.mn);
if (R.mn != cur.mn) tmp.push_back(R.mn);
tmp.push_back(L.mn2); tmp.push_back(R.mn2);
cur.mn2 = tmp.empty() ? INT_MAX : *min_element(tmp.begin(), tmp.end());
// second max
tmp.clear();
if (L.mx != cur.mx) tmp.push_back(L.mx);
if (R.mx != cur.mx) tmp.push_back(R.mx);
tmp.push_back(L.mx2); tmp.push_back(R.mx2);
cur.mx2 = tmp.empty() ? INT_MIN : *max_element(tmp.begin(), tmp.end());
// count of min/max
cur.cnt_mn = 0;
if (L.mn == cur.mn) cur.cnt_mn += L.cnt_mn;
if (R.mn == cur.mn) cur.cnt_mn += R.cnt_mn;
cur.cnt_mx = 0;
if (L.mx == cur.mx) cur.cnt_mx += L.cnt_mx;
if (R.mx == cur.mx) cur.cnt_mx += R.cnt_mx;
}
void build(int idx, int l, int r) {
if (l == r) {
seg[idx] = {0,0,INT_MAX,INT_MIN,1,1,-1};
return;
}
int mid = (l + r)/2;
build(idx*2, l, mid);
build(idx*2+1, mid+1, r);
push_up(idx);
}
// push lazy assignment to children
void push_down(int idx) {
if (seg[idx].lazy != -1) {
int val = seg[idx].lazy;
auto &L = seg[idx*2], &R = seg[idx*2+1];
L.mn = L.mx = val;
L.mn2 = INT_MAX; L.mx2 = INT_MIN;
L.cnt_mn = L.cnt_mx = (L.mn2==INT_MAX ? 1 : 1);
L.lazy = val;
R.mn = R.mx = val;
R.mn2 = INT_MAX; R.mx2 = INT_MIN;
R.cnt_mn = R.cnt_mx = (R.mn2==INT_MAX ? 1 : 1);
R.lazy = val;
seg[idx].lazy = -1;
}
}
// chmax (add phase)
void range_chmax(int idx, int l, int r, int ql, int qr, int val) {
if (r < ql || l > qr || seg[idx].mx <= val) return;
if (ql <= l && r <= qr && seg[idx].mn < val && seg[idx].mx > val) {
push_down(idx);
int mid = (l+r)/2;
range_chmax(idx*2, l, mid, ql, qr, val);
range_chmax(idx*2+1, mid+1, r, ql, qr, val);
push_up(idx);
return;
}
if (ql <= l && r <= qr && seg[idx].mn < val && seg[idx].mx <= val) {
seg[idx].mn = seg[idx].mx = val;
seg[idx].mn2 = INT_MAX;
seg[idx].mx2 = INT_MIN;
seg[idx].cnt_mn = seg[idx].cnt_mx = r-l+1;
seg[idx].lazy = val;
return;
}
push_down(idx);
int mid = (l+r)/2;
range_chmax(idx*2, l, mid, ql, qr, val);
range_chmax(idx*2+1, mid+1, r, ql, qr, val);
push_up(idx);
}
// chmin (remove phase)
void range_chmin(int idx, int l, int r, int ql, int qr, int val) {
if (r < ql || l > qr || seg[idx].mn >= val) return;
if (ql <= l && r <= qr && seg[idx].mx > val && seg[idx].mn < val) {
push_down(idx);
int mid = (l+r)/2;
range_chmin(idx*2, l, mid, ql, qr, val);
range_chmin(idx*2+1, mid+1, r, ql, qr, val);
push_up(idx);
return;
}
if (ql <= l && r <= qr && seg[idx].mx > val && seg[idx].mn >= val) {
seg[idx].mn = seg[idx].mx = val;
seg[idx].mn2 = INT_MAX;
seg[idx].mx2 = INT_MIN;
seg[idx].cnt_mn = seg[idx].cnt_mx = r-l+1;
seg[idx].lazy = val;
return;
}
push_down(idx);
int mid = (l+r)/2;
range_chmin(idx*2, l, mid, ql, qr, val);
range_chmin(idx*2+1, mid+1, r, ql, qr, val);
push_up(idx);
}
// collect result
void collect(int idx, int l, int r, int finalHeight[]) {
if (l == r) {
finalHeight[l] = seg[idx].mn;
return;
}
push_down(idx);
int mid = (l+r)/2;
collect(idx*2, l, mid, finalHeight);
collect(idx*2+1, mid+1, r, finalHeight);
}
void buildWall(int n_, int k, int op[], int left[], int right[],
int height[], int finalHeight[]) {
n = n_;
build(1,0,n-1);
for (int i=0;i<k;i++){
if(op[i]==1) range_chmax(1,0,n-1,left[i],right[i],height[i]);
else range_chmin(1,0,n-1,left[i],right[i],height[i]);
}
collect(1,0,n-1,finalHeight);
}
