#include "wall.h" #include <bits/stdc++.h> #define pb push_back #define fst first #define snd second #define fore(i,a,b) for(int i=a,pao=b;i<pao;++i) #define SZ(x) ((int)x.size()) #define ALL(x) x.begin(),x.end() #define mset(a,v) memset((a),(v),sizeof(a)) #define FIN ios::sync_with_stdio(0);cin.tie(0);cout.tie(0) using namespace std; typedef long long ll; #include <ext/pb_ds/assoc_container.hpp> using namespace __gnu_pbds; template <typename T> using indexed_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; const int MAXN=2e6; struct Nodo{ int mini=0,maxi=INT_MAX; Nodo():mini(0),maxi(INT_MAX){}; Nodo(int a, int b){ mini=a,maxi=b; } }; int N; Nodo st[MAXN*4]; void apply(int x,Nodo h){ st[x].mini=max(st[x].mini,h.mini); st[x].maxi=max(st[x].maxi,st[x].mini); st[x].maxi=min(st[x].maxi,h.maxi); st[x].mini=min(st[x].mini,st[x].maxi); } void push(int v){ apply(v*2,st[v]); apply(v*2+1,st[v]); st[v]=Nodo(); } void upd(int ts,int te,Nodo h,int v=1,int s=0,int e=N-1){ if(e<ts||te<s)return; if(ts<=s&&e<=te){ apply(v,h); return; }else{ push(v); int m=(s+e)/2; upd(ts,te,h,v*2,s,m); upd(ts,te,h,v*2+1,m+1,e); } } int que(int k,int v=1,int s=0,int e=N-1){ if(s==k&&e==k){ return st[v].mini; } push(v); int m=(s+e)/2; if(k<=m){ return que(k,v*2,s,m); }else return que(k,v*2+1,m+1,e); } void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){ N=n; fore(i,0,k){ if(op[i]==1){ upd(left[i],right[i],Nodo(height[i],INT_MAX)); }else{ upd(left[i],right[i],Nodo(0,height[i])); } } fore(i,0,n)finalHeight[i]=que(i); return; }