#988910 (C++17) No.2786 RMQ on Grid Path

提出ソース
結果

問題	No.2786 RMQ on Grid Path
コンテスト
ユーザー	shkiiii_
提出日時	2024-06-14 23:47:42
言語	C++17 (gcc 13.3.0 + boost 1.87.0)
結果	AC
実行時間	734 ms / 6,000 ms
コード長	7,392 bytes
コンパイル時間	3,109 ms
コンパイル使用メモリ	218,468 KB
最終ジャッジ日時	2025-02-21 22:28:09
ジャッジサーバーID （参考情報）	judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン	結果
sample	AC * 2
other	AC * 35
権限があれば一括ダウンロードができます
ソースコード

raw source code
#include<bits/stdc++.h>
// #include<atcoder/all>
// #include<boost/multiprecision/cpp_int.hpp>

using namespace std;
// using namespace atcoder;
// using bint = boost::multiprecision::cpp_int;
using ll = long long;
using ull = unsigned long long;
using P = pair<ll,ll>;
using vi = vector<ll>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
#define rep(i,n) for(ll i = 0;i < (ll)n;i++)
#define ALL(x) (x).begin(),(x).end()
#define sz(c) ((ll)(c).size())
#define LB(A,x) (int)(lower_bound(A.begin(),A.end(),x)-A.begin())
#define UB(A,x) (int)(upper_bound(A.begin(),A.end(),x)-A.begin())
// #define MOD 1000000007
#define MOD 998244353
template<typename T>using min_priority_queue=priority_queue<T,vector<T>,greater<T>>;
template<typename T>ostream&operator<<(ostream&os,vector<T>&v){for(int i = 0;i < v.size();i++)os<<v[i]<<(i+1!=v.size()?" ":"");return os;}
template<typename T>istream&operator>>(istream&is,vector<T>&v){for(T&in:v)is>>in;return is;}
template<typename T1,typename T2>ostream&operator<<(ostream&os,pair<T1,T2>&p){os<<p.first<<" "<<p.second;return os;}
template<typename T1,typename T2>istream&operator>>(istream&is,pair<T1,T2>&p){is>>p.first>>p.second;return is;}

class UnionFind{
  public:
  vector<int> par;
  UnionFind(long long size) : par(size,-1){}

  bool unite(int x,int y){
    x = root(x),y = root(y);
    if(x == y)return false;
    if(par[y] < par[x])swap(x,y);
    par[x] += par[y];
    par[y] = x;
    return true;
  }

  bool find(int x,int y){
    return root(x) == root(y);
  }

  int root(int x){
    return par[x] < 0 ? x : par[x] = root(par[x]);
  }

  int size(int x){
    return -par[root(x)];
  }
};
// https://beet-aizu.github.io/library/tree/heavylightdecomposition.cpp
struct HLD{
  /*
  v := 隣接リスト
  id := 元々の頂点のHLD後の頂点番号。
  head := heavyな辺でつながれた頂点集合の代表元。もっとも浅い頂点。
  sub_sz := 部分木のサイズ
  par := 親
  inv := HLD後の頂点番号から元々の頂点番号をかえす

  add_edge(a,b) := a,b間の無向辺を追加
  build() := HLD 分解を実行。内部でdfs_szによる部分木の取得、dfs_hldによるHLD実行。
  lca(a,b) := a,bのLCAを返す
  for_each(a,b,f) := 頂点a,b間の頂点(a,bを含む)にfを実行。このfにseg木などが乗る。
  for_each_edge(a,b,f) := 頂点a,b間の辺にfを実行。辺はつながっている２つの頂点の内深い方と対応させる。
  */
  vector<vector<int>> v;
  vector<int> id,head,sub_sz,par,inv;
  HLD(int n) : v(n),id(n,-1),head(n),sub_sz(n,1),par(n,-1),inv(n){}

  void add_edge(int a,int b){
    v[a].push_back(b);
    v[b].push_back(a);
  }

  void dfs_sz(int ov,int pre){
    if(v[ov].size() && v[ov][0] == pre)swap(v[ov][0],v[ov].back());
    par[ov] = pre;
    for(auto &nv : v[ov]){
      if(nv == pre)continue;
      dfs_sz(nv,ov);
      sub_sz[ov] += sub_sz[nv];
      if(sub_sz[nv] > sub_sz[v[ov][0]])swap(nv,v[ov][0]);
    }
  }
  void dfs_hld(int ov,int &pos){
    id[ov] = pos++;
    inv[id[ov]] = ov;
    for(auto nv : v[ov]){
      if(nv == par[ov])continue;
      head[nv] = (nv == v[ov][0] ? head[ov] : nv);
      dfs_hld(nv,pos);
    }
  }
  void build(int root = 0){
    int pos = 0;
    dfs_sz(root,-1);
    head[root] = root;
    dfs_hld(root,pos);
  }
  int lca(int a,int b){
    while(1){
      if(id[a] > id[b])swap(a,b);
      if(head[a] == head[b])return a;
      b = par[head[b]];
    }
  }
  /*
  関数内でfは半開区間で値を取得するように正規化するので，
  BITが閉区間で実装されている場合などは
  auto f = [&](int a,int b){return bit.sum(a,b-1);};
  の様に変更する．データ構造が半開区間で値を取得する場合は
  auto f = [&](int a,int b){return seg.get(a,b);};
  でよい．
  実装を見ればわかるが，a,bに対応する部分は
  hld.idで正規化されて渡されているので外部でfの宣言をするために正規化する必要はない.
  */
  template<typename F>
  void for_each(int a,int b,const F& f){
    while(1){
      if(id[a] > id[b])swap(a,b);
      f(max(id[head[b]],id[a]),id[b]+1);
      if(head[a] != head[b])b = par[head[b]];
      else break;
    }
  }
  template<typename F>
  void for_each_edge(int a,int b,const F& f){
    while(1){
      if(id[a] > id[b])swap(a,b);
      if(head[a] != head[b]){
        f(id[head[b]],id[b]+1);
        b = par[head[b]];
      }else{
        if(a != b)f(id[a]+1,id[b]+1);
        break;
      }
    }
  }
};
template<typename T>
class Segtree{
  public:
  using F = function<T(T,T)>;
  int n;
  F f;
  T ti;
  vector<T> dat;
  Segtree(){};
  Segtree(F f,T ti): f(f),ti(ti){}
  void init(int N){
    n = 1;
    while(n < N)n <<= 1;
    dat.assign(n << 1,ti);
  }
  void build(const vector<T> &v){
    int N = v.size();
    init(N);
    for(int i = 0;i < N;i++)dat[n+i] = v[i];
    for(int i = n-1;i >= 0;i--)dat[i] = f(dat[(i << 1)|0],dat[(i << 1)|1]);
  }
  void set(int k,T x){
    dat[k+=n] = x;
    while(k >>= 1){
      dat[k] = f(dat[(k << 1)|0],dat[(k << 1)|1]);
    }
  }
  T get(int l,int r){
    T vl = ti,vr = ti;
    for(l += n,r += n;l < r;l >>= 1,r >>= 1){
      if(l & 1)vl = f(vl,dat[l++]);
      if(r & 1)vr = f(dat[--r],vr);
    }
    return f(vl,vr);
  }
  // max t s.t. check(query(st,t))
  template<typename C>
  int bs(int st,C &check,T &acc,int k,int l,int r){
    if(r-l <= 1){
      acc = f(acc,dat[k]);
      return check(acc) ? k-n : -1;
    }
    int mid = (l+r) >> 1;
    if(mid <= st)return bs(st,check,acc,(k << 1)|1,mid,r);
    if(st <= l && !check(f(acc,dat[k]))){
      acc = f(acc,dat[k]);
      return -1;
    }
    int vl = bs(st,check,acc,(k << 1)|0,l,mid);
    if(vl != -1)return vl;
    return bs(st,check,acc,(k << 1)|1,mid,r);
  }
  template<typename C>
  int bs(int st,C &check){
    T acc = ti;
    return bs(st,check,acc,1,0,n);
  }
};

int dx[] = {-1,0,0,1};
int dy[] = {0,1,-1,0};

int main(){
  
  ios_base::sync_with_stdio(0), cin.tie(0);
  int h,w;
  cin >> h >> w;
  vvi a(h,vi(w));
  rep(i,h)cin >> a[i];
  UnionFind uf(h*w+100);
  vvi e(h*w+1);
  rep(i,h)rep(j,w){
    e[a[i][j]].emplace_back(i*w+j);
  }
  vector<vector<P>> v(h*w);
  rep(i,h*w+1){
    for(auto au : e[i]){
      int oi = au/w,oj = au%w;
      rep(_,4){
        int ni = oi + dy[_],nj = oj + dx[_];
        if(ni < 0 || ni >= h || nj < 0 || nj >= w)continue;
        if(a[ni][nj] <= i){
          if(uf.unite(au,ni*w+nj)){
            v[au].emplace_back(ni*w+nj,i);
          }
        }
      }
    }
  }
  HLD hld(h*w);
  rep(i,h*w){
    for(auto au : v[i]){
      hld.add_edge(au.first,i);
    }
  }
  hld.build();
  auto f = [](ll a,ll b){return max(a,b);};
  Segtree<ll> seg(f,-1);
  {
    vi init(h*w,-1);
    rep(i,h*w){
      for(auto au : v[i]){
        if(hld.par[i] == au.first){
          init[hld.id[i]] = au.second;
        }else{
          init[hld.id[au.first]] = au.second;
        }
      }
    }
    // cout << init << " a\n";
    seg.build(init);
  }
  int Q;cin >> Q;
  while(Q--){
    int rs,cs,rt,ct;cin >> rs >> cs >> rt >> ct;
    rs--;cs--;rt--;ct--;
    rs = rs*w+cs;rt = rt*w+ct;
    ll res = 0;
    auto g = [&](int l,int r){
      res = max(res,seg.get(l,r));
    };
    hld.for_each_edge(rs,rt,g);
    cout << res << "\n";
  }
  /*
  rep(i,h*w){
    for(auto au : v[i]){
      cout << i << " " << au << "\n";
    }
  }
  */
  

  

  return 0;
}
yukicoder

結果

ソースコード
