< hamamuさんのAI生成コード置き場

単調ヒストグラム走査

日時はサーバーが記録したものです。更新すると更新日時が変わるので、不都合がある場合は新しく投稿してください。

//generated by GPT-5.6 Terra, modified by hamamu
namespace MonotoneHistogramRasterIndexSpace{
using Int = long long;
using ll  = long long;

struct MonotoneHistogramRasterCore{
    vector<ll> H; //H[i]: 列 i の高さ。広義単調増加列
    ll N=0; //列数

    /*
    smH[i]:
      H[0]+...+H[i-1] を、
      「高さ 0 以上になる直前までの総和」を基準にずらしたもの。

      これにより、
        smH[split] + h*(N-split)
      が、そのまま行0基準の符号付き面積になる。
    */
    vector<ll> smH;

    /*
    高さが変化しない区間ごとの情報。
    行 bottom[t] から行 nextBottom-1 までは、列 [left[t],N-1] にセルが存在。
    endArea[t]: その区間の上端の行までにある、行0基準の符号付きセル数
    */
    vector<ll> bottom;
    vector<ll> left;
    vector<ll> width;
    vector<ll> endArea;

    MonotoneHistogramRasterCore() = default;
    MonotoneHistogramRasterCore(const vector<Int> &H_){ Init(H_); }

    //---- H を受け取って構築。計算量 O(N)
    void Init(const vector<Int> &H_){
        assert(!H_.empty());
        H.assign(H_.begin(),H_.end());
        N=(ll)H.size();
        for(ll i=1;i<N;++i) assert(H[i-1]<=H[i]); //広義単調増加列かcheck

        //-- まず通常の累積和を作る
        smH.assign(N+1,0);
        for(ll i=0;i<N;++i)
            smH[i+1]=smH[i]+H[i];

        /*
        高さ 0 以上になる直前までの総和を引き、
        smH を「行0基準」の累積和へ変換
        */
        ll split0=lower_bound(H.begin(),H.end(),0LL)-H.begin();
        ll base=smH[split0];
        for(ll i=0;i<=N;++i)
            smH[i]-=base;

        //-- 高さ区間情報を初期化する
        bottom.clear();
        left.clear();
        width.clear();
        endArea.clear();

        /*
        行H[0]-1 以下は、常に全列にセルがある。
        そこは bottomSelect 側の等幅尾部として扱い、
        ここでは行 H[0] 以上の「幅が変化しうる部分」だけを圧縮する。

        currentHeight: 現在構築する高さ区間の下端
        split: H[i] > currentHeight となる最初の列。
          すなわち、行 currentHeight における最左列。
        */
        ll currentHeight=H[0];
        ll split=upper_bound(H.begin(),H.end(),currentHeight)-H.begin();

        //-- 同じ高さをまとめ、各高さ区間を一つずつ作る
        while(split<N){
            //-- 次に現れる高さ
            ll nextHeight=H[split];

            //-- H[i]==nextHeight となる範囲 [split,next) を求める
            ll next=split;
            while(next<N && H[next]==nextHeight) ++next;

            /*
            行 currentHeight から行 nextHeight-1 では、
            セルが存在する列は常に [split,N-1]。

            その区間の上端、すなわち行 nextHeight-1 までの
            行0基準の符号付き面積は
              smH[split] + nextHeight * count(H[i] >= nextHeight)
            で計算できる。
            */
            ll areaToNextHeight=smH[split]+nextHeight*(N-split);

            //-- 高さ区間を保存する
            bottom.push_back(currentHeight);
            left.push_back(split);
            width.push_back(N-split);
            endArea.push_back(areaToNextHeight);

            //-- 次の高さ区間へ進む
            currentHeight=nextHeight;
            split=next;
        }
    }

    /* 行sjから行ejまでの符号付き面積  O(log N) */
    Int area(ll sj,ll ej) const{
        if (sj==0) return areaBelow(ej); //高速化
        else       return areaBelow(ej)-areaBelow(sj-1);
    }

    Int leftAt(ll j) const{ //行j最左位置 N:行が空
        //行jにセルがある条件は H[i]>j
        return (Int)(upper_bound(H.begin(),H.end(),j)-H.begin());
    }
    Int widthAt(ll j) const{ return (Int)(N-leftAt(j)); }//行j幅
    Int rightAt(ll j) const{ return (Int)(N-1); } //行j最右位置

    /* セル(i,j)の行0基準ラスタ順位  1-origin、左下が1 */
    Int bottomRank(ll i,ll j) const{
        assert(contains(i,j));
        //-- 自分より下にあるセル数 + 行内での左からの順位
        return areaBelow(j-1)+(Int)(i-leftAt(j)+1);
    }

    /* セル(i,j)の行sj基準ラスタ順位  1-origin、左下が1 */
    Int bottomRank(ll i,ll j,ll sj) const{
        //-- 行sjより下の面積を引く
        return bottomRank(i,j)-areaBelow(sj-1);
    }

    /* セル(i,j)の最上行基準逆ラスタ順位  1-origin、左上が1 */
    Int topRank(ll i,ll j) const{
        assert(contains(i,j));
        //-- 自分より上にあるセル数 + 行内での左からの順位
        return area(j+1,H.back()-1)+(Int)(i-leftAt(j)+1);
    }

    /* セル(i,j)の行sj基準逆ラスタ順位  1-origin、左上が1 */
    Int topRank(ll i,ll j,ll sj) const{
        //-- 行sjより上にあるセル数を引く
        return topRank(i,j)-area(sj+1,H.back()-1);
    }

    /* 下からラスタ順位S(1-origin、左下1、S≦0可)のセル(i,j)  なし:{-1,-1} */
    pair<Int,Int> bottomSelect(ll S) const{
        /*
        行 H[0]-1 以下は幅 N の等幅尾部である。
        その最上段までの符号付き面積を求める。
        */
        ll tailEnd=areaBelow(H[0]-1);
        if(S<=tailEnd){//等幅尾部に入る場合は、直接戻す
            ll d=tailEnd-S;
            ll i=N-1-d%N;
            ll j=H[0]-1-d/N;
            return {(Int)i,(Int)j};
        }

        /*
        それより上は、圧縮した高さ区間に入る。
        endArea の最後を超える順位は存在しない。
        */
        if(endArea.empty() || endArea.back()<S)
            return {-1,-1};

        ll t=lower_bound(endArea.begin(),endArea.end(),S)-endArea.begin();

        ll previousArea=(t==0 ? tailEnd : endArea[t-1]);//区間t直前までの面積
        ll offset=S-previousArea-1; //区間t内での 0-origin 順位
        ll i=left[t]  +offset%width[t];
        ll j=bottom[t]+offset/width[t];

        return {(Int)i,(Int)j};
    }

    /* 行sjからラスタ順位S(1-origin、左下1、S≦0可)のセル(i,j) なし:{-1,-1} */
    pair<Int,Int> bottomSelect(ll S,ll sj) const{
        //-- 部分領域内の順位を全体順位へ変換する
        return bottomSelect((ll)areaBelow(sj-1)+S);
    }

    /* 上からラスタ順位S(1-origin、左上が1)にあるセル(i,j) */
    pair<Int,Int> topSelect(ll S) const{
        if(S<=0) return {-1,-1};
        ll top=H.back()-1; //最上段の行番号
        ll upperArea=area(H[0],top);//幅が変化しうる有限部分[H[0],top]の面積

        if(S>upperArea){//等幅尾部のとき 各行は幅N、左端0
            ll d=S-upperArea-1;
            ll i=d%N;
            ll j=(H[0]-1)-d/N;
            return {(Int)i,(Int)j};
        }

        /*
        高さ区間tの「さらに上」のセル数はareaBelow(top)-endArea[t]
        よって、endArea[t-1] <= areaBelow(top)-S < endArea[t]
        を満たす区間 t に答がある。
        */
        ll topArea=areaBelow(top);
        ll t=upper_bound(endArea.begin(),endArea.end(),topArea-S)-endArea.begin();
        ll nextBottom=(t+1<(ll)bottom.size() ? bottom[t+1] : H.back());

        ll cellsAbove=topArea-endArea[t];//区間 t より上の面積にあるセル数
        ll offset=S-cellsAbove-1;//区間tの上端側から見た 0-origin offset
        ll i=left[t]       +offset%width[t];
        ll j=(nextBottom-1)-offset/width[t];
        return {(Int)i,(Int)j};
    }

    /*
    行sj以下の部分を上からラスタ順に見て、S 番目のセルを返す。O(log N)
    - S は 1-origin
    - セルが存在しないときは {-1,-1}
    */
    pair<Int,Int> topSelect(ll S,ll sj) const{
        ll skipped=area(sj+1,H.back()-1); //行sjより上のセル数
        return topSelect(skipped+S);
    }

    /*
    有効セル (si,sj) からラスタ距離 d だけ進んだ位置を返す。
    d は負でもよい。
    セルが存在しないときは {-1,-1}
    */
    pair<Int,Int> bottomStep(ll si,ll sj,ll d) const{
        return bottomSelect((ll)bottomRank(si,sj)+d);
    }

    /*
    有効セル (si,sj) から逆ラスタ距離 d だけ進んだ位置を返す。
    d は負でもよい。
    セルが存在しないときは {-1,-1}
    */
    pair<Int,Int> topStep(ll si,ll sj,ll d) const{
        return topSelect((ll)topRank(si,sj)+d);
    }

    /*
    (si,sj) から (ei,ej) までのラスタ順における符号付き距離。
    後なら正、前なら負、同じなら 0。
    */
    Int bottomDistance(ll si,ll sj,ll ei,ll ej) const{
        return bottomRank(ei,ej)-bottomRank(si,sj);
    }

    /*
    (si,sj) から (ei,ej) までの逆ラスタ順における符号付き距離。
    後なら正、前なら負、同じなら 0。
    */
    Int topDistance(ll si,ll sj,ll ei,ll ej) const{
        return topRank(ei,ej)-topRank(si,sj);
    }

    bool contains(ll i,ll j) const{return 0<=i && i<N && j<H[i];}//true:セル(i,j)存在

private:
    /* 行0から行jまでの符号付き面積  O(log N) */
    Int areaBelow(ll j) const{
        ll h=j+1;
        ll split=lower_bound(H.begin(),H.end(),h)-H.begin();
        return (Int)(smH[split]+(N-split)*h);
    }
};

/* Hが広義単調増加/減少、セルがH[i]の下側/上側 の4通りに対応するラッパー */
struct MonotoneHistogramRasterIndex{
    MonotoneHistogramRasterCore core;

    ll N=0;
    bool upper=false;    //true: セルは H[i] 以上
    bool reverseX=false; //内部座標で横方向を反転したか

    ll bottomStart=0; //bottomRank / bottomSelect の既定開始行
    ll topStart=0;    //topRank / topSelect の既定開始行

    MonotoneHistogramRasterIndex() = default;
    MonotoneHistogramRasterIndex(const vector<Int> &H_,bool upper_){ Init(H_,upper_); }

    /*
    H_ とセルの向きから構築する。計算量 O(N)。
        upper==false:  セル(i,j)が存在  <=>  j < H[i]
        upper==true:   セル(i,j)が存在  <=>  H[i] <= j
    */
    void Init(const vector<Int> &H_,bool upper_){
        assert(!H_.empty());
        N=(ll)H_.size();
        upper=upper_;

        bool increasing=true;
        bool decreasing=true;

        //-- H が単調増加・単調減少のどちらかを確認する
        for(ll i=1;i<N;++i){
            if(H_[i-1]>H_[i]) increasing=false;
            if(H_[i-1]<H_[i]) decreasing=false;
        }
        assert(increasing || decreasing);

        /*
        core の正規形は「K[x] が広義単調増加」「セル(x,y)が存在 <=> y<K[x]」。
        upper 側セルは y=-j-1, K=-H により正規形へ直す。
        さらに K が減少してしまう場合は x 軸も反転する。
        */
        reverseX=(increasing==upper);

        vector<Int> K(N);
        for(ll i=0;i<N;++i){
            ll x=reverseX ? N-1-i : i;
            K[x]=upper ? -H_[i] : H_[i];
        }

        core.Init(K); //変換後の K は広義単調増加になっている

        /*
        下側セルでは下へ無限に続くため、bottom 系の既定開始行は 0。
        上側セルでは最下行が存在するため、その最下行を既定開始行にする。
        */
        bottomStart=upper ? *min_element(H_.begin(),H_.end()) : 0;

        /*
        下側セルでは最上行が存在するため、top 系の既定開始行は最上行。
        上側セルでは上へ無限に続くため、仕様どおり行0を既定開始行にする。
        */
        topStart=upper ? 0 : *max_element(H_.begin(),H_.end())-1;
    }

    Int area(ll sj,ll ej) const{
        if(upper) return core.area(-ej-1,-sj-1);//上側セル時、上下反転かつ入替
        else      return core.area(sj,ej);
    }

    Int leftAt(ll j) const{//行j左端位置
        return !reverseX ? core.leftAt(toY(j)) : (Int)(N-1-core.rightAt(toY(j)));
    }
    Int widthAt(ll j) const{ return core.widthAt(toY(j)); }//行j幅
    Int rightAt(ll j) const{ return leftAt(j)+widthAt(j)-1; }//行j右端位置

    Int bottomRank(ll i,ll j) const{ return bottomRank(i,j,bottomStart); }
    Int bottomRank(ll i,ll j,ll sj) const{
        assert(contains(i,j));
        ll x=toX(i), y=toY(j), sy=toY(sj); //元座標と内部座標へ変換

        //下側(上側)セルの物理ラスタ順は core の bottom(top) 順
        ll S=upper ? core.topRank(x,y,sy) : core.bottomRank(x,y,sy);
        return (Int)fixRankX(S,x,y); //横反転時は行内順位補正
    }

    Int topRank(ll i,ll j) const{ return topRank(i,j,topStart); }
    Int topRank(ll i,ll j,ll sj) const{
        assert(contains(i,j));
        ll x=toX(i), y=toY(j), sy=toY(sj); //元座標と内部座標へ変換

        //下側(上側)セルの物理逆ラスタ順は core の top(bottom) 順
        ll S=upper ? core.bottomRank(x,y,sy) : core.topRank(x,y,sy);
        return (Int)fixRankX(S,x,y); //横反転時は行内順位補正
    }

    pair<Int,Int> bottomSelect(ll S) const{ return bottomSelect(S,bottomStart); }
    pair<Int,Int> bottomSelect(ll S,ll sj) const{
        ll sy=toY(sj);
        //下側(上側)セルの物理ラスタ順は core の bottom(top) 順
        auto [x,y]=upper ? core.topSelect(S,sy) : core.bottomSelect(S,sy);
        if(x<0) return {-1,-1}; //core側で範囲外なら、そのまま返す
        x=fixSelectX(x,y); //横反転時は、行内位置を反転
        return {(Int)fromX(x),(Int)fromY(y)}; //物理座標へ戻す
    }

    pair<Int,Int> topSelect(ll S) const{ return topSelect(S,topStart); }
    pair<Int,Int> topSelect(ll S,ll sj) const{
        ll sy=toY(sj);
        //下側(上側)セルの物理逆ラスタ順は core の top(bottom) 順
        auto [x,y]=upper ? core.bottomSelect(S,sy) : core.topSelect(S,sy);
        if(x<0) return {-1,-1}; //core側で範囲外なら、そのまま返す
        x=fixSelectX(x,y); //横反転時は、行内位置を反転
        return {(Int)fromX(x),(Int)fromY(y)}; //物理座標へ戻す
    }

    pair<Int,Int> bottomStep(ll si,ll sj,ll d) const{ return bottomSelect((ll)bottomRank(si,sj)+d); }
    pair<Int,Int>    topStep(ll si,ll sj,ll d) const{ return    topSelect((ll)   topRank(si,sj)+d); }
    Int bottomDistance(ll si,ll sj,ll ei,ll ej) const{ return bottomRank(ei,ej)-bottomRank(si,sj); }
    Int    topDistance(ll si,ll sj,ll ei,ll ej) const{ return    topRank(ei,ej)-   topRank(si,sj); }

private:
    ll toX(ll i) const{ //物理座標 i を core 側の x 座標へ変換
        return reverseX ? N-1-i : i;
    }
    ll fromX(ll x) const{ //core 側の x 座標を物理座標 i へ変換
        return reverseX ? N-1-x : x;
    }
    ll toY(ll j) const{ //物理座標 j を core 側の y 座標へ変換
        return upper ? -j-1 : j;
    }
    ll fromY(ll y) const{ //core 側の y 座標を物理座標 j へ変換
        return upper ? -y-1 : y;
    }
    bool contains(ll i,ll j) const{ return core.contains(toX(i),toY(j)); }//true:セル(i,j)存在

    /* 横反転時、core内のx昇順順位を、元座標でのi昇順順位へ直す */
    ll fixRankX(ll S,ll x,ll y) const{
        if(!reverseX) return S;
        ll pos=x-core.leftAt(y)+1; //coreでの行内 1-origin 順位
        return S+core.widthAt(y)-2*pos+1; //行内順序だけを反転する
    }

    /* 横反転時、coreが返したセルを同一行内で反転 */
    ll fixSelectX(ll x,ll y) const{
        if(!reverseX) return x;
        ll left=core.leftAt(y), width=core.widthAt(y);
        return left+width-1-(x-left); //[left,left+width-1]内で左右反転
    }
};
} // namespace MonotoneHistogramRasterIndexSpace
using MonotoneHistogramRasterIndexSpace::MonotoneHistogramRasterIndex;
/*
単調増加or減少の高さ列Hが与えられたときの、横走査を扱うクラス

H={0,2,2,3,5,6}、セルが下側と上側の様子
j    下側              j    上側
5・・・・・□          5□□□□□・
4・・・・□□          4□□□□・・
3・・・・□□          3■■■★・・
2・・・□□□          2■■■・・・
1・■■■★□          1■・・・・・
0・■■■■■          0■・・・・・
. 0 1 2 3 4 5 i        . 0 1 2 3 4 5 i

.bottomRank(4,1)=9     .bottomRank(3,3)=9
.bottomSelect(9)={4,1} ,bottomSelect(9)={3,3}

- Hは空配列不可
- ラスタ順＝左下起点、逆ラスタ順＝左上起点 とする

MonotoneHistogramRasterIndex hc(H,false); //セルがHの下側
MonotoneHistogramRasterIndex hc(H,true);  //セルがHの上側

ll i=hc.leftAt (j);  //行jの左端位置
ll i=hc.rightAt(j);  //行jの右端位置
ll w=hc.widthAt(j);  //行jの幅

ll S=hc.area(sj,ej);      //行[sj,ej]の面積
ll S=hc.bottomRank(i,j);    //行0   から(i,j)までの  ラスタ順位1-origin(=面積)
ll S=hc.bottomRank(i,j,sj); //行sj  から(i,j)までの  ラスタ順位1-origin(=面積)
ll S=hc.topRank(i,j);       //最上行から(i,j)までの逆ラスタ順位1-origin(=面積)
ll S=hc.topRank(i,j,sj);    //行sj  から(i,j)までの逆ラスタ順位1-origin(=面積)

以下全て S:1-origin、S≦0可、セルなし:(-1,-1)
auto[i,j]=hc.bottomSelect(S);    //行0 から    ラスタ順位Sの(i,j)
auto[i,j]=hc.bottomSelect(S,sj); //行sjから    ラスタ順位Sの(i,j)
auto[i,j]=hc.topSelect(S);       //最上行から逆ラスタ順位Sの(i,j)
auto[i,j]=hc.topSelect(S,sj);    //行sj  から逆ラスタ順位Sの(i,j)

以下全て d≦0可、セルなし:(-1,-1)
auto[i,j]=hc.bottomStep(si,sj,d);  //(si,sj)から  ラスタ距離dの(i,j)
auto[i,j]=hc.topStep(si,sj,d);     //(si,sj)から逆ラスタ距離dの(i,j)

ll d=hc.bottomDistance(si,sj,ei,ej); //(si,sj)から(ei,ej)の  ラスタ距離
ll d=hc.topDistance   (si,sj,ei,ej); //(si,sj)から(ei,ej)の逆ラスタ距離

- 負への拡張
  - 縦方向のセル存在を、[0,Hi-1]ではなく[-∞,Hi-1]とする
  - 負のHiも可
*/