#include "wall.h"
#include <iostream>
#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;
int mx;
segtree* left;
segtree* right;
segtree* parent;
segtree();
segtree(int L, int R, segtree* P);
void enable(int i, int op, int height);
void disable(int i);
int rangemin(int L, int R);
int rangemax(int L, int R);
void printmax();
void printmin();
};
vector<int> enable[2000000];
vector<int> disable[2000000];
segtree V[1000000];
int vcount = -1;
segtree::segtree()
{
mn = 1e5 + 1;
mx = 0;
}
segtree::segtree(int L, int R, segtree* P)
{
l = L;
r = R;
parent = P;
mn = 1e5 + 1;
mx = 0;
if(l == r) return;
int m = (l+r+2)/2 - 1; //for -1
vcount++;
left = &V[vcount];
*left = segtree(l, m, this);
vcount++;
right = &V[vcount];
*right = segtree(m+1, r, this);
}
void segtree::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);
mx = max(left->mx, right->mx);
}
}
else
{
if(l == r) mn = height;
else
{
left->enable(i, 2, height);
right->enable(i, 2, height);
mn = min(left->mn, right->mn);
}
}
}
void segtree::disable(int i)
{
if(i < l || r < i) return;
if(l == r)
{
mn = 1e5+1;
mx = 0;
}
else
{
left->disable(i);
right->disable(i);
mx = max(left->mx, right->mx);
mn = min(left->mn, right->mn);
}
}
int segtree::rangemin(int L, int R)
{
if(R < l || r < L) return 1e5+1;
if(L <= l && r <= R)
{
return mn;
}
return min(left->rangemin(L, R), right->rangemin(L, R));
}
int segtree::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));
}
void segtree::printmax()
{
if(left == NULL) cout << mx << ' ';
else
{
left->printmax();
right->printmax();
}
}
void segtree::printmin()
{
if(left == NULL) cout << mn << ' ';
else
{
left->printmin();
right->printmin();
}
}
segtree* T;
int N;
int K;
int binary_search_res(int a, int b, segtree* X)
{
while(a < X->l || X->r < b) X = X->parent;
while(X->left != NULL && b <= (X->l + X->r + 2)/2 - 1) X = X->left;
while(X->right != NULL && a > (X->l + X->r + 2)/2 - 1) X = X->right;
// cout << "search " << a << ' ' << b << '\n';
if(a == b)
{
if(X->rangemin(a, a) == 1e5+1) return X->rangemin(a+1, K-1);
else return X->rangemax(a+1, K-1);
}
int m = (a+b+2)/2-1+1;
// cout << m << ' ' << T->rangemin(m, N-1) << ' ' << T->rangemax(m, N-1) << '\n';
if(X->rangemin(m, K-1) <= X->rangemax(m, K-1)) return binary_search_res(m, b, X);
else return binary_search_res(a, m-1, X);
}
//1 = max, 2 = min
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
N = n;
K = k;
segtree S(-1, k-1, NULL);
S.enable(-1, 2, 0);
T = &S;
for(int j = 0; j < k; j++)
{
enable[left[j]].push_back(j);
disable[right[j]].push_back(j);
}
int temp = 0;
for(int i = 0; i < n; i++)
{
// cout << "i = " << i << '\n';
for(int j: enable[i])
{
S.enable(j, op[j], height[j]);
// cout << "enable " << j << '\n';
// S.printmax();
// cout << '\n';
// S.printmin();
// cout << '\n';
}
if(enable[i].size() != 0 || (i > 0 && disable[i-1].size() != 0))
{
temp = binary_search_res(-1, k-1, T);
// cout << temp << '\n';
// cout << "\n\n\n";
}
for(int j: disable[i])
{
S.disable(j);
// cout << "disable " << j << '\n';
// S.printmax();
// cout << '\n';
// S.printmin();
// cout << "\n\n\n";
}
finalHeight[i] = temp;
}
}
