#include "wall.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <unordered_set>
using namespace std;
vector<pair<int,int> >st(1e7, make_pair(0,0));
void add(int p, int l, int r, int a, int b, int h){
if (p!=1){
int pare=p/2;
st[p].first=max(min(st[p].first, st[pare].second), st[pare].first);
st[p].second=min(max(st[p].second, st[pare].first), st[pare].second);
}
if (a<=l && b>=r){
st[p].first=max(st[p].first, h);
st[p].second=max(st[p].second, h);
return;
}
else if (b<l or a>r) return;
int m=(l+r)/2;
add(p*2, l, m, a, b, h);
add(p*2+1, m+1, r, a, b, h);
st[p].first=min(st[p*2].first, st[p*2+1].first);
st[p].second=max(st[p*2].second, st[p*2+1].second);
//cout << "p " << p << " " << l << " " << r << " vals " << st[p].first << " " << st[p].second << "\n";
return;
}
void remove(int p, int l, int r, int a, int b, int h){
if (p!=1){
int pare=p/2;
st[p].first=max(min(st[p].first, st[pare].second), st[pare].first);
st[p].second=min(max(st[p].second, st[pare].first), st[pare].second);
}
if (a<=l && b>=r){
st[p].first=min(st[p].first, h);
st[p].second=min(st[p].second, h);
return;
}
else if (b<l or a>r) return;
int m=(l+r)/2;
remove(p*2, l, m, a, b, h);
remove(p*2+1, m+1, r, a, b, h);
st[p].first=min(st[p*2].first, st[p*2+1].first);
st[p].second=max(st[p*2].second, st[p*2+1].second);
return;
}
void fin(int p, int l, int r, int* finalHeight){
if (p!=1){
int pare=p/2;
st[p].first=max(min(st[p].first, st[pare].second), st[pare].first);
st[p].second=min(max(st[p].second, st[pare].first), st[pare].second);
}
if (l==r){
finalHeight[l]=st[p].first;
return;
}
int m=(l+r)/2;
fin(2*p, l, m, finalHeight);
fin(2*p+1, m+1, r, finalHeight);
return;
}
void buildWall (int n, int k, int* op, int* left, int* right, int* height, int* finalHeight){
for (int i=0; i<k; i++){
int a=left[i], b=right[i];
if (op[i]==1) add(1, 0, n-1, a, b, height[i]);
else remove(1, 0, n-1, a, b, height[i]);
//fin(1, 0, n-1, finalHeight);
}fin(1, 0, n-1, finalHeight);
return;
}
