#include "wall.h" #include <bits/stdc++.h> using namespace std; #define MOD1 1000000007 #define MOD2 998244353 #define fir first #define sec second #define pushf push_front #define pushb push_back #define popf pop_front #define popb pop_back #define mp make_pair #define all(a) a.begin(), a.end() #define lbound(v, x) lower_bound(all(v), x) - v.begin() #define ubound(v, x) upper_bound(all(v), x) - v.begin() #define chmax(a, b) a = max(a, b) #define chmin(a, b) a = min(a, b) #define FOR1(a) for (int _ = 0; _ < (a); ++_) #define FOR2(i, a) for (int i = 0; i < (a); ++i) #define FOR3(i, a, b) for (int i = (a); i < (b); ++i) #define RFOR1(a) for (int _ = (a)-1; _ >= 0; --_) #define RFOR2(i, a) for (int i = (a)-1; i >= 0; --i) #define RFOR3(i, a, b) for (int i = (b)-1; i >= (a); --i) #define overload3(a, b, c, d, ...) d // Always choose the fourth argument to call. Hence, which function to call is determined by the number of given arguments. #define REP(...) overload3(__VA_ARGS__, FOR3, FOR2, FOR1)(__VA_ARGS__) #define RREP(...) overload3(__VA_ARGS__, RFOR3, RFOR2, RFOR1)(__VA_ARGS__) typedef long long ll; typedef pair<int, int> pii; typedef vector<int> vi; typedef pair<ll, ll> pll; typedef vector<ll> vll; typedef vector<bool> vb; typedef vector<char> vc; typedef vector<string> vs; typedef vector<pii> vpii; typedef vector<pll> vpll; typedef vector<vi> vvi; typedef vector<vll> vvll; typedef vector<vb> vvb; typedef vector<vc> vvc; typedef vector<vpii> vvpii; typedef vector<vpll> vvpll; typedef queue<int> qi; typedef queue<ll> qll; typedef queue<pii> qpii; typedef queue<pll> qpll; typedef deque<int> dqi; typedef deque<ll> dqll; typedef deque<pii> dqpii; typedef deque<pll> dqpll; typedef priority_queue<int> pqi; typedef priority_queue<ll> pqll; typedef priority_queue<pii> pqpii; typedef priority_queue<pll> pqpll; typedef priority_queue<int, vi, greater<int> > r_pqi; typedef priority_queue<ll, vll, greater<ll> > r_pqll; typedef priority_queue<pii, vpii, greater<pii> > r_pqpii; typedef priority_queue<pll, vpll, greater<pll> > r_pqpll; const ll inf = 1e16; vll ans; struct node { int n; vll lmax, lmin; node(int size = 0) : n(size) { lmax.assign(4 * n, inf); lmin.assign(4 * n, 0); } void apply(int ind, ll v) { if(v > 0) { lmin[ind] = chmax(lmin[ind], v); lmax[ind] = chmax(lmax[ind], lmin[ind]); } else { lmax[ind] = chmin(lmax[ind], -v); lmin[ind] = chmin(lmin[ind], lmax[ind]); } // cerr<<ind<<' '<<lmax[ind]<<' '<<lmin[ind]<<' '<<v<<endl; } void push(int ind) { if(lmax[ind] < inf) { apply(2 * ind, -lmax[ind]); apply(2 * ind + 1, -lmax[ind]); lmax[ind] = inf; } if(lmin[ind] > 0) { apply(2 * ind, lmin[ind]); apply(2 * ind + 1, lmin[ind]); lmin[ind] = 0; } } void update(int ql, int qr, ll v, int ind = 1, int l = 0, int r = -1) { if(r == -1) { r = n-1; } if(ql > r || l > qr) return; if(ql <= l && r <= qr) { apply(ind, v); return; } push(ind); int mid = (l + r) / 2; update(ql, qr, v, 2 * ind, l, mid); update(ql, qr, v, 2 * ind + 1, mid + 1, r); } void query(int ind = 1, int l = 0, int r = -1) { if(r == -1) r = n-1; if(l == r) { ans[l] = lmin[ind]; return; } // cerr<<l<<' '<<r<<' '<<ind<<' '<<lmin[ind]<<' '<<endl; push(ind); int mid = (l + r) / 2; query(2 * ind, l, mid); query(2 * ind + 1, mid + 1, r); } }; void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){ ans = vll(n); node root(n); REP(i, k) { root.update(left[i], right[i], height[i] * (op[i] == 1 ? 1 : -1)); } root.query(); REP(i, n) { finalHeight[i] = ans[i]; } return; } // int main() // { // int n; // int k; // int i, j; // int status = 0; // status = scanf("%d%d", &n, &k); // assert(status == 2); // int* op = (int*)calloc(sizeof(int), k); // int* left = (int*)calloc(sizeof(int), k); // int* right = (int*)calloc(sizeof(int), k); // int* height = (int*)calloc(sizeof(int), k); // int* finalHeight = (int*)calloc(sizeof(int), n); // for (i = 0; i < k; i++){ // status = scanf("%d%d%d%d", &op[i], &left[i], &right[i], &height[i]); // assert(status == 4); // } // buildWall(n, k, op, left, right, height, finalHeight); // for (j = 0; j < n; j++) // printf("%d\n", finalHeight[j]); // return 0; // }