ACL 遅延セグ木を二分探索 min_left, max_right

Skyscraper

  • 問題 https://jonathanirvin.gs/files/division2_3d16774b0423.pdf
  • 自分の高さまで遠くを見ることができる
  • クエリとして
    • 1「建物iから見える建物の数を答える」
    • 2「範囲で高さ更新」
    • 3「単体の高さ更新」
    • というのが飛んでくる
  • O(Q log(N) log(N))で書いたらTLEしたため、min_left, max_rightが必要になった

f:id:peroon:20210210143724p:plain

input

8 6
4 2 3 2 4 7 6 5
1 3
1 2
2 3 8
1 5
3 5 7 1
1 8

output

3
1
2
5

input, output コメントつき

// input
8 6
4 2 3 2 4 7 6 5

// クエリ
1 3 // 建物3から見える建物の数は？
1 2
2 3 8 // 建物3の高さを8にする
1 5
3 5 7 1 // 建物5~7の高さを1にする
1 8

// output
3
1
2
5

全てのクエリを終えた時の建物の状態

f:id:peroon:20211026011640p:plain

AC code

#ifdef LOCAL
    #define _GLIBCXX_DEBUG
    #define __clock__
#else
    #pragma GCC optimize("Ofast")
#endif
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using VI = vector<ll>;
using VV = vector<VI>;
using VS = vector<string>;
using PII = pair<ll, ll>;

#define FOR(i,a,b) for(ll i=(a);i<(b);++i)
#define rep(i,b) FOR(i, 0, b)
#define ALL(v) (v).begin(), (v).end()
#define p(s) cout<<(s)<<'\n'
#define p2(s, t) cout << (s) << " " << (t) << '\n'
#define br() p("")
#define pn(s) cout << (#s) << " " << (s) << '\n'
#define SZ(x) ((int)(x).size())
#define SORT(A) sort(ALL(A))
#define RSORT(A) sort(ALL(A), greater<ll>())

const ll mod = 1e9 + 7;
// const ll mod = 998244353;
const ll inf = 1e18;
const double PI = acos(-1);

#include <atcoder/lazysegtree>
using namespace atcoder; // 忘れがち

using S = long long;
using F = long long;

const S INF = 8e18;
const F ID = 8e18;

S op(S a, S b){ return std::max(a, b); }
S e(){ return -INF; }
S mapping(F f, S x){ return (f == ID ? x : f); }
F composition(F f, F g){ return (f == ID ? g : f); }
F id(){ return ID; }

// min_left, max_right用
ll global_h;
bool g(S x){
  return x <= global_h;
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    ll N,Q;cin>>N>>Q;
    VI A(N);
    rep(i,N)cin>>A[i];

    // 範囲更新、範囲MAXの遅延セグ木
    lazy_segtree<S, op, e, F, mapping, composition, id> seg(A);

    while(Q--){
      ll ty;cin>>ty;
      if(ty==1){
        // print
        ll i;cin>>i;i--;
        ll h = seg.get(i);

        // この素朴な二分探索では クエリごとに O(log(N) log(N))となってしまい、TLEします（まず素朴解法でWAではないことを確認）
        // ll cnt=1;
        // 左にいくつ見える？
        // ll ma = seg.prod(0,i);
        // if(ma<=h){
        //   // 全部見える
        //   cnt += i;
        // }else{
        //   // 二分探索必要
        //   ll left=0; // can't
        //   ll right=i; // can
        //   while(left+1!=right){
        //     ll center = (left+right)/2;
        //     if(seg.prod(center,i+1)<=h){
        //       right=center;
        //     }else{
        //       left=center;
        //     }
        //   }
        //   cnt += i-right;
        // }
        // 右にいくつ見える？
        // ma = seg.prod(i,N);
        // if(ma<=h){
        //   // 全部見える
        //   cnt += N-i-1;
        // }else{
        //   ll left=i; // can
        //   ll right=N; // can't
        //   while(left+1!=right){
        //     ll center = (left+right)/2;
        //     if(seg.prod(i,center+1)<=h){
        //       left=center;
        //     }else{
        //       right=center;
        //     }
        //   }
        //   cnt += left-i;
        // }

        // セグ木内の二分探索により、クエリごとにO(log(N))となり、ACします
        global_h = h; // 関数g用
        ll r = seg.max_right<g>(i); // iより右でどこまで見えるか
        ll l = seg.min_left<g>(i); // iより左でどこまで見えるか
        ll cnt = r-l;
        p(cnt);
      }
      else if(ty==2){
        // set height
        ll i;cin>>i;i--;
        ll h;cin>>h;
        seg.set(i,h);
      }
      else{
        // range update
        ll i,j,h;cin>>i>>j>>h;
        i--;j--;
        seg.apply(i,j+1,h);
      }
    }

    return 0;
}