#include <bits/stdc++.h> using namespace std; #define ll int #define ff first #define ss second #define pb push_back #define all(x) (x).begin(),(x).end() #define ertunt return struct segtree{ vector<ll>a,b; segtree(ll n){ a.assign(4*n,0); b.assign(4*n,1000000000); } void push(ll v){ ll x=v*2,y=x+1; a[x]=max(a[x],a[v]); b[x]=min(b[x],b[v]); if(a[x]>b[x]) a[x]=b[x]; a[y]=max(a[y],a[v]); b[y]=min(b[y],b[v]); if(a[y]>b[y]) a[y]=b[y]; a[v]=0; b[v]=1000000000; } void upd1(ll v,ll l,ll r,ll L,ll R,ll val){ if(R<l||r<L)ertunt; if(L<=l&&r<=R){ a[v]=max(a[v],val); b[v]=max(b[v],val); ertunt; } push(v); ll m=(l+r)>>1; upd1(v*2,l,m,L,R,val); upd1(v*2+1,m+1,r,L,R,val); } void upd2(ll v,ll l,ll r,ll L,ll R,ll val){ if(R<l||r<L)ertunt; if(L<=l&&r<=R){ b[v]=min(b[v],val); if(a[v]>b[v]) a[v]=b[v]; ertunt; } push(v); ll m=(l+r)>>1; upd2(v*2,l,m,L,R,val); upd2(v*2+1,m+1,r,L,R,val); } void get(ll v,ll l,ll r,int H[]){ if(l==r){ if(a[v]>b[v]) a[v]=b[v]; H[l]=a[v]; ertunt; } push(v); ll m=(l+r)>>1; get(v*2,l,m,H); get(v*2+1,m+1,r,H); } }; void buildWall(int n,int k,int op[],int l[],int r[],int h[],int H[]){ segtree t(n); for(ll i=0;i<k;i++){ if(op[i]==1) t.upd1(1,0,n-1,l[i],r[i],h[i]); } for(ll i=0;i<k;i++){ if(op[i]==2) t.upd2(1,0,n-1,l[i],r[i],h[i]); } t.get(1,0,n-1,H); }