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

BIT矩形加算矩形和

投稿者hamamu
言語C++23
更新日時 (JST)2026-11-16 03:12:24
サイズ4,878 Byte
参照URL

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

テキストで開く
#pragma once

//published at https://yukicoder.me/users/10411/ai_code/80
//generated by GPT-6.1 Sol modified by hamamu
template<class T>
struct RectangleAddRectangleSum{
    using ll  = long long;
    //以下、x座標を左→右、y座標を下→上として説明や変数を付けている
private:
    // 内部区間は[l,r)×[b,t)。右端の次を保持し、長さを座標差で扱う。
    struct Add{ ll l,r,b,t; T z; };
    struct Query{ ll l,r,b,t; };

    // a*X*Y + b*X + c*Y + d を表す4係数
    struct Coeff{
        T a=T(), b=T(), c=T(), d=T();
        void add(const Coeff &v){ a+=v.a, b+=v.b, c+=v.c, d+=v.d; }
    };

    vector<Add> adds;      //加算長方形
    vector<Query> queries; //取得長方形

public:
    void add(ll l,ll r,ll b,ll t,const T &z){
        assert(l<=r && b<=t);
        adds.push_back({l,r+1,b,t+1,z});
    }
    void query(ll l,ll r,ll b,ll t){
        assert(l<=r && b<=t);
        queries.push_back({l,r+1,b,t+1});
    }

    vector<T> solve()const{
        ll N=(ll)adds.size(), Q=(ll)queries.size();
        vector<T> ret(Q);
        if(N==0 || Q==0) return ret;

        //---- y方向の座標圧縮
        // y方向は加算の境界だけを座圧する。計算時には元の座標を使う。
        vector<ll> ys;
        for(const auto &a:adds){
            ys.push_back(a.b);
            ys.push_back(a.t);
        }
        sort(ys.begin(),ys.end());
        ys.erase(unique(ys.begin(),ys.end()),ys.end());
        auto index=[&](ll y)->ll{
            return (ll)(lower_bound(ys.begin(),ys.end(),y)-ys.begin());
        };

        //---- 加算イベントの生成
        // 元の登録内容を残し、作業用コピーのb,tを圧縮添字に置き換える。
        // x=lで開始、x=rで終了する2イベントを作る(内部は半開区間)。
        auto addsC=adds;
        vector<pair<ll,ll>> updates; //加算イベント <x座標, addsのindex + 終了なら+N>
        for(ll i=0;i<N;++i){
            auto &a=addsC[i];
            a.b=index(a.b), a.t=index(a.t);
            updates.emplace_back(a.l,i);
            updates.emplace_back(a.r,i+N);
        }
        sort(updates.begin(),updates.end());

        //---- 取得イベントの生成
        // 各取得をF(r,b,t)-F(l,b,t)に分ける。
        // F(X,b,t)は、x<Xかつb<=y<tの和。yの検索も走査前に済ませる。
        vector<pair<ll,ll>> asks;  //取得イベント <x座標, queriesのindex + r側なら+Q>
        vector<pair<ll,ll>> yi(Q); //yi[i]: queries[i]のy方向の圧縮添字 <b,t>
        for(ll i=0;i<Q;++i){
            const auto &q=queries[i];
            yi[i]={index(q.b),index(q.t)};
            asks.emplace_back(q.l,i);
            asks.emplace_back(q.r,i+Q);
        }
        sort(asks.begin(),asks.end());

        //---- 4係数を管理するBITの準備
        // 長方形内加算を「点(s,t)の右上全点へz加算…★」4つに分解。
        // ★の「点(X,Y)の左下総和」への寄与は、
        // (X,Y)が(s,t)の右上のとき z*(X-s)*(Y-t) = zXY-ztX-zsY+zst
        // XY,X,Y,定数の4係数であるz,-zt,-zs,zstを、1本のBITにまとめて載せる。
        ll M=(ll)ys.size();
        vector<Coeff> bit(M+1);
        auto apply=[&](ll i,ll s,const T &z){ //加算をBITに反映
            ll t=ys[i];
            Coeff v{z,T(-z*t),T(-z*s),T(z*s*t)};
            for(ll j=i+1;j<=M;j+=j&-j) bit[j].add(v);
        };
        auto prefix=[&](ll k,ll X,ll Y)->T{ //左下総和取得
            Coeff v;
            // Yより下にある加算境界の係数を、BITから合計する
            for(ll j=k;j>0;j-=j&-j) v.add(bit[j]);
            return T((v.a*X+v.c)*Y+v.b*X+v.d);
        };

        //---- x方向の平面走査
        ll j=0; //次の加算イベントの添字
        for(auto [x,id]:asks){
            //-- 取得境界xより左の加算イベントをBITに反映
            while(j<2*N && updates[j].first<x){
                auto [a,k]=updates[j++];
                const auto &u=addsC[k<N ? k : k-N];
                T z=u.z;
                if(k>=N) z=-z;
                apply(u.b,a,z);
                apply(u.t,a,-z);
            }
            //-- y区間の和を求め、答えに加減算
            ll i=id<Q ? id : id-Q; //元のクエリ番号
            const auto &q=queries[i];
            auto [b,t]=yi[i];
            T sum=prefix(t,x,q.t)-prefix(b,x,q.b);
            if(id<Q) sum=-sum;
            ret[i]+=sum;
        }

        return ret;
    }
};
/*
- ---- 定義・準備 ----
RectangleAddRectangleSum<T> solver; //Tに型を指定
solver.add(l,r,b,t,z); //[l,r]×[b,t]にz加算を登録
solver.query(l,r,b,t); //[l,r]×[b,t]の和を取得登録
- ---- 和取得 ----
auto ret=solver.solve(); // vector<T>。i番目に登録した取得の答えがret[i]
*/