#include <iostream>
#include "wall.h"
#include <algorithm>
#include <vector>
using namespace std;
//Maintain a set of updates, update it at left and right points of every update
//Sort the updates by index
//Segtree over update indices
void q(int i)
{
cout << i << '\n';
}
struct segtree
{
int l;
int r;
int mn = 1e5+1;
int mx = 0;
int mn_pos;
int mx_pos;
segtree* left = NULL;
segtree* right = NULL;
segtree()
{
;
}
segtree(int L, int R)
{
l = L;
r = R;
mn_pos = r;
mx_pos = r;
if(l == r) return;
int m = (l+r+2)/2 - 1; //for -1
left = new segtree(l, m);
right = new segtree(m+1, r);
}
void enable(int i, int op, int height)
{
if(i < l || r < i) return;
if(op == 1)
{
if(l == r) mx = height;
else
{
left->enable(i, 1, height);
right->enable(i, 1, height);
if(left->mx <= right->mx)
{
mx = right->mx;
mx_pos = right->mx_pos;
}
else
{
mx = left->mx;
mx_pos = left->mx_pos;
}
}
}
else
{
if(l == r) mn = height;
else
{
left->enable(i, 0, height);
right->enable(i, 0, height);
if(left->mn >= right->mn)
{
mn = right->mn;
mn_pos = right->mn_pos;
}
else
{
mn = left->mn;
mn_pos = left->mn_pos;
}
}
}
}
void disable(int i)
{
if(i < l || r < i) return;
if(l == r)
{
mn = 1e5+1;
mx = 0;
}
else
{
left->disable(i);
right->disable(i);
if(left->mx <= right->mx)
{
mx = right->mx;
mx_pos = right->mx_pos;
}
if(left->mn >= right->mn)
{
mn = right->mn;
mn_pos = right->mn_pos;
}
}
}
int compute()
{
if(right->mn <= right->mx) return right->compute(); //√
else if(left->mn > right->mx && left->mx < right->mn)
{
if(left->mn_pos <= left->mx_pos) return right->mn;
else return right->mx;
}
else if(left->mn <= right->mx)
{
return right->mx;
}
else if(left->mx >= right->mn)
{
return right->mn;
}
else return left->compute();
}
void printmin()
{
if(left == NULL)
{
// if(mn == 1e5+1) cout << "mx" << ' ';
// else cout << mn << ' ';
}
else
{
left->printmin();
right->printmin();
}
}
void printmax()
{
if(left == NULL)
{
// cout << mx << ' ';
}
else
{
left->printmax();
right->printmax();
}
}
int rangemin(int L, int R)
{
if(R < l || r < L) return 1e5+1;
if(L <= l && r <= R)
{
// cout << "returning " << l << ' ' << r << ' ' << mn << '\n';
return mn;
}
return min(left->rangemin(L, R), right->rangemin(L, R));
}
int rangemax(int L, int R)
{
if(R < l || r < L) return 0;
if(L <= l && r <= R) return mx;
return max(left->rangemax(L, R), right->rangemax(L, R));
}
};
segtree* T;
int N;
int binary_search_res(int a, int b)
{
// cout << "binary search " << a << ' ' << b << '\n';
if(a == b)
{
// cout << a << ' ' << T->rangemin(a, a) << ' ' << T->rangemin(a+1, N-1) << ' ' << T->rangemax(a+1, N-1) << '\n';
if(T->rangemin(a, a) == 1e5+1) return T->rangemin(a+1, N-1);
else return T->rangemax(a+1, N-1);
}
int m = (a+b)/2+1;
if(a == -1 && b == 0) m = 0;
// cout << m << ' ' << T->rangemin(m, N-1) << ' ' << T->rangemax(m, N-1) << '\n';
// for(int i = m; i <= N-1; i++) cout << T->rangemin(i, i) << ' ';
// cout << '\n';
if(T->rangemin(m, N-1) <= T->rangemax(m, N-1)) return binary_search_res(m, b);
else return binary_search_res(a, m-1);
}
//1 = max, 2 = min
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
N = n;
segtree S(-1, n-1);
S.enable(-1, 2, 0);
T = &S;
vector<int> enable[n], disable[n];
// cout << k << '\n';
for(int j = 0; j < k; j++)
{
// cout << j << ' ' << left[j] << ' ' << right[j] << '\n';
enable[left[j]].push_back(j);
disable[right[j]].push_back(j);
}
// cout << '\n';
int temp = 0;
for(int i = 0; i < n; i++)
{
// cout << "i = " << i << '\n';
if(enable[i].size() != 0 || disable[i].size() != 0)
{
for(int j: enable[i])
{
// cout << "enable " << j << '\n';
S.enable(j, op[j], height[j]);
// cout << "max ";
// for(int k = -1; k < n; k++) cout << S.rangemax(k, k) << ' ';
// cout << '\n';
// cout << "min ";
// for(int k = -1; k < n; k++) cout << S.rangemin(k, k) << ' ';
// cout << '\n';
// cout << '\n';
}
temp = binary_search_res(-1, N-1);
for(int j: disable[i])
{
// cout << "disable " << j << '\n';
S.disable(j);
// cout << "max ";
// for(int k = -1; k < n; k++) cout << S.rangemax(k, k) << ' ';
// cout << '\n';
// cout << "min ";
// for(int k = -1; k < n; k++) cout << S.rangemin(k, k) << ' ';
// cout << '\n';
// cout << '\n';
}
}
finalHeight[i] = temp;
}
}
