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]
*/