/**
____ ____ ____ __________________ ____ ____ ____
||I || ||c || ||e || || || ||M || ||a || ||n ||
||__|| ||__|| ||__|| ||________________|| ||__|| ||__|| ||__||
|/__\| |/__\| |/__\| |/________________\| |/__\| |/__\| |/__\|
*/
#include <iostream>
#include <chrono>
#include <vector>
#include <algorithm>
#include "wall.h"
#define maxn 2000005
#define maxlog 20
#define INF 1000000010
#define LINF 1000000000000000005
#define endl '\n'
#define pb(x) push_back(x)
#define X first
#define Y second
#define control cout<<"passed"<<endl;
using namespace std;
typedef pair <int, int> pii;
typedef long long ll;
typedef pair <ll, ll> pll;
typedef pair <int, ll> pil;
typedef pair <ll, int> pli;
typedef long double ld;
std::chrono::high_resolution_clock::time_point startT, currT;
constexpr double TIME_MULT = 1;
double timePassed()
{
using namespace std::chrono;
currT = high_resolution_clock::now();
double time = duration_cast<duration<double>>(currT - startT).count();
return time * TIME_MULT;
}
int lazy[maxn * 4];
pii tree[maxn * 4];
void push_lazy(int node, int l, int r)
{
if(lazy[node] == -1)
return;
tree[node].X = lazy[node];
tree[node].Y = lazy[node];
if(l != r)
{
lazy[node * 2] = lazy[node];
lazy[node * 2 + 1] = lazy[node];
}
lazy[node] = -1;
}
void _remove(int node, int l, int r, int ql, int qr, int qval)
{
push_lazy(node, l, r);
if(ql > r || qr < l)
return;
if(tree[node].Y <= qval)
return;
if(l >= ql && r <= qr && tree[node].X >= qval)
{
lazy[node] = qval;
push_lazy(node, l, r);
return;
}
int mid = (l + r) / 2;
_remove(node * 2, l, mid, ql, qr, qval);
_remove(node * 2 + 1, mid + 1, r, ql, qr, qval);
tree[node].Y = max(tree[node * 2].Y , tree[node * 2 + 1].Y);
tree[node].X = min(tree[node * 2].X , tree[node * 2 + 1].X);
}
void add(int node, int l, int r, int ql, int qr, int qval)
{
push_lazy(node, l, r);
if(ql > r || qr < l)
return;
if(tree[node].X >= qval)
return;
if(l >= ql && r <= qr && tree[node].Y <= qval)
{
lazy[node] = qval;
push_lazy(node, l, r);
return;
}
int mid = (l + r) / 2;
add(node * 2, l, mid, ql, qr, qval);
add(node * 2 + 1, mid + 1, r, ql, qr, qval);
tree[node].Y = max(tree[node * 2].Y , tree[node * 2 + 1].Y);
tree[node].X = min(tree[node * 2].X , tree[node * 2 + 1].X);
}
int ans[maxn];
void answer(int node , int l , int r)
{
push_lazy(node , l , r);
if(l == r)
{
ans[l - 1] = tree[node].X;
return;
}
int mid = (l + r) / 2;
answer(node * 2 , l , mid);
answer(node * 2 + 1 , mid + 1 , r);
}
int pom[maxn];
void buildWall(int n , int k , int op[] , int left[] , int right[] , int height[] , int finalHeight[])
{
n++;
for(int i = 0; i < 4 * maxn; i++)
lazy[i] = -1 , tree[i] = {0 , 0};
for(int i = 0; i < k; i++)
if(op[i] == 1)
add(1 , 1 , n , left[i] + 1 , right[i] + 1 , height[i]);
else
_remove(1 , 1 , n , left[i] + 1 , right[i] + 1 , height[i]);
answer(1 , 1 , n);
for(int i = 0; i < n - 1; i++)
finalHeight[i] = ans[i];
}
/**int main()
{
#ifdef ONLINE_JUDGE
freopen("input.in", "r", stdin);
freopen("output.out", "w", stdout);
#endif
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
///startT = std::chrono::high_resolution_clock::now();
add(1 , 1 , 10 , 2 , 9 , 4);
_remove(1 , 1 , 10 , 5 , 10 , 1);
_remove(1 , 1 , 10 , 4 , 7 , 5);
add(1 , 1 , 10 , 1 , 6 , 3);
add(1 , 1 , 10 , 3 , 3 , 5);
_remove(1 , 1 , 10 , 7 , 8 , 0);
answer(1 , 1 , 10);
for(int i = 0; i < 10; i++)
cout << ans[i] << " ";
cout << endl;
return 0;
}
*/
