#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 vector<ll>f(200005),inv(200005); ll mod = 998244353; ll modpow(ll a, ll b){ ll res = 1; while(b){ if(b&1){ res*=a; res%=mod; } a*=a; a%=mod; b >>= 1; } ertunt res; } ll nCk(ll n, ll k){ if(k < 0 || k > n) ertunt 0; ertunt 1ll*f[n]*inv[k]%mod*inv[n-k]%mod; } void buildWall(int n, int k, int op[], int l[], int r[], int h[], int H[]){ for(ll i = 0; i < n; i++) H[i] = 0; vector<array<ll,3>> add, rem; for(ll i = 0; i < k; i++){ if(op[i] == 1) add.pb({h[i], l[i], r[i]}); else rem.pb({h[i], l[i], r[i]}); } sort(all(add), [](const array<ll,3> &a, const array<ll,3> &b){ return a[0] > b[0]; }); sort(all(rem), [](const array<ll,3> &a, const array<ll,3> &b){ if(a[0] != b[0]) return a[0] < b[0]; if(a[1] != b[1]) return a[1] < b[1]; return a[2] < b[2]; }); vector<ll> brov(n, -1); for(ll i = 0; i < (ll)add.size(); i++){ ll x = add[i][0], L = add[i][1], R = add[i][2]; ll j = L; while(j <= R){ if(brov[j] != -1){ j = brov[j] + 1; continue; } ll t = j; while(t <= R && brov[t] == -1){ if(H[t] == 0){ H[t] = x; } brov[t] = R; t++; } j = t; } } brov.assign(n, -1); for(ll i = 0; i < (ll)rem.size(); i++){ ll x = rem[i][0], L = rem[i][1], R = rem[i][2]; ll j = L; while(j <= R){ if(brov[j] != -1){ j = brov[j] + 1; continue; } ll t = j; while(t <= R && brov[t] == -1){ if(H[t] > x) H[t] = x; brov[t] = R; t++; } j = t; } } }