#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; } }