#pragma once //published at https://yukicoder.me/users/10411/ai_code/80 //generated by GPT-6.1 Sol modified by hamamu template 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 adds; //加算長方形 vector 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 solve()const{ ll N=(ll)adds.size(), Q=(ll)queries.size(); vector ret(Q); if(N==0 || Q==0) return ret; //---- y方向の座標圧縮 // y方向は加算の境界だけを座圧する。計算時には元の座標を使う。 vector 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> updates; //加算イベント for(ll i=0;i> asks; //取得イベント vector> yi(Q); //yi[i]: queries[i]のy方向の圧縮添字 for(ll i=0;i 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=N) z=-z; apply(u.b,a,z); apply(u.t,a,-z); } //-- y区間の和を求め、答えに加減算 ll i=id 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。i番目に登録した取得の答えがret[i] */