Static Rectangle Add Rectangle Sum
(DataStructure/staticrectaddrectsum.hpp)

• View this file on GitHub
• Last update: 2023-01-17 01:58:11+09:00
• Include: #include "DataStructure/staticrectaddrectsum.hpp"

Depends on

• Binary Indexed Tree (DataStructure/bit.hpp)
• Static Rectangle Sum (DataStructure/staticrectsum.hpp)

Verified with

• Verify/LC_static_rectangle_add_rectangle_sum.test.cpp

Code

#pragma once

#include "DataStructure/staticrectsum.hpp"
template<typename T>struct StaticRectangleAddRectangleSum{
    StaticRectangleSum<T> bit[4]; //XY,X,Y,Const
    struct Rect{int l,d,r,u;};
    vector<Rect> que;
    StaticRectangleAddRectangleSum(){}
    void add(int x,int y,T w){
        bit[0].add(x,y,w);
        bit[1].add(x,y,w*-y);
        bit[2].add(x,y,w*-x);
        bit[3].add(x,y,w*x*y);
    }
    void add(int l,int d,int r,int u,T w){
        add(l,d,w);
        add(l,u,-w);
        add(r,d,-w);
        add(r,u,w);
    }
    void query(int l,int d,int r,int u){
        que.push_back({l,d,r,u});
    }
    vector<T> run(){
        int q=que.size();
        for(auto& [l,d,r,u]:que){
            rep(j,0,4){
                bit[j].query(0,0,l,d);
                bit[j].query(0,0,l,u);
                bit[j].query(0,0,r,d);
                bit[j].query(0,0,r,u);
            }
        }
        auto XY=bit[0].run();
        auto X=bit[1].run();
        auto Y=bit[2].run();
        auto Const=bit[3].run();
        vector<T> res(q);
        rep(i,0,q){
            auto [l,d,r,u]=que[i];
            res[i]+=XY[4*i]*l*d;
            res[i]+=X[4*i]*l;
            res[i]+=Y[4*i]*d;
            res[i]+=Const[4*i];

            res[i]-=XY[4*i+1]*l*u;
            res[i]-=X[4*i+1]*l;
            res[i]-=Y[4*i+1]*u;
            res[i]-=Const[4*i+1];

            res[i]-=XY[4*i+2]*r*d;
            res[i]-=X[4*i+2]*r;
            res[i]-=Y[4*i+2]*d;
            res[i]-=Const[4*i+2];

            res[i]+=XY[4*i+3]*r*u;
            res[i]+=X[4*i+3]*r;
            res[i]+=Y[4*i+3]*u;
            res[i]+=Const[4*i+3];
        }
        return res;
    }
};

/**
 * @brief Static Rectangle Add Rectangle Sum
*/

#line 2 "DataStructure/staticrectaddrectsum.hpp"

#line 2 "DataStructure/bit.hpp"

template<typename T>struct BIT{
    int n; T all=0; vector<T> val;
    BIT(int _n=0):n(_n),val(_n+10){}
    void clear(){val.assign(n+10,0); all=T();}
    void add(int i,T x){
        for(i++;i<=n;i+=(i&-i))val[i]=val[i]+x;
        all+=x;
    }
    T sum(int i){
        T res=0;
        for(;i;i-=(i&-i))res+=val[i];
        return res;
    }
    T sum(int L,int R){return sum(R)-sum(L);} // [L,R)

    int lower_bound(T x){
        int ret=0,len=1;
        while(2*len<=n)len<<=1;
        for(;len>=1;len>>=1){
            if(ret+len<=n and val[ret+len]<x){
                ret+=len;
                x-=val[ret];
            }
        }
        return ret;
    }
};

/**
 * @brief Binary Indexed Tree
 */
#line 3 "DataStructure/staticrectsum.hpp"

template<class T>struct StaticRectangleSum{
    struct P{
        ll x,y; T w;
    };
    struct Rect{
        ll l,d,r,u;
    };
    struct Q{
        ll x,d,u,id,inv;
    };
    vector<P> plus;
    vector<Rect> que;
    StaticRectangleSum(){}
    void add(ll x,ll y,T w){
        plus.push_back({x,y,w});
    }
    void query(ll l,ll d,ll r,ll u){
        que.push_back({l,d,r,u});
    }
    vector<T> run(){
        ll n=plus.size(),q=que.size();
        sort(ALL(plus),[](P& p,P& q){return p.y<q.y;});
        vector<ll> ys;
        rep(i,0,n)ys.push_back(plus[i].y);
        ys.erase(unique(ALL(ys)),ys.end());
        rep(i,0,n)plus[i].y=lower_bound(ALL(ys),plus[i].y)-ys.begin();
        vector<Q> qs;
        rep(i,0,q){
            auto& [l,d,r,u]=que[i];
            d=lower_bound(ALL(ys),d)-ys.begin();
            u=lower_bound(ALL(ys),u)-ys.begin();
            qs.push_back({l,d,u,i,1});
            qs.push_back({r,d,u,i,-1});
        }
        sort(ALL(plus),[](P& p,P& q){return p.x<q.x;});
        sort(ALL(qs),[](Q& p,Q& q){return p.x<q.x;});
        vector<T> res(q);
        ll k=0;
        BIT<T> bit(ys.size());
        for(auto& q:qs){
            while(k<n and plus[k].x<q.x){
                bit.add(plus[k].y,plus[k].w);
                k++;
            }
            res[q.id]+=bit.sum(q.u,q.d)*q.inv;
        }
        return res;
    }
};

/**
 * @brief Static Rectangle Sum
*/
#line 4 "DataStructure/staticrectaddrectsum.hpp"
template<typename T>struct StaticRectangleAddRectangleSum{
    StaticRectangleSum<T> bit[4]; //XY,X,Y,Const
    struct Rect{int l,d,r,u;};
    vector<Rect> que;
    StaticRectangleAddRectangleSum(){}
    void add(int x,int y,T w){
        bit[0].add(x,y,w);
        bit[1].add(x,y,w*-y);
        bit[2].add(x,y,w*-x);
        bit[3].add(x,y,w*x*y);
    }
    void add(int l,int d,int r,int u,T w){
        add(l,d,w);
        add(l,u,-w);
        add(r,d,-w);
        add(r,u,w);
    }
    void query(int l,int d,int r,int u){
        que.push_back({l,d,r,u});
    }
    vector<T> run(){
        int q=que.size();
        for(auto& [l,d,r,u]:que){
            rep(j,0,4){
                bit[j].query(0,0,l,d);
                bit[j].query(0,0,l,u);
                bit[j].query(0,0,r,d);
                bit[j].query(0,0,r,u);
            }
        }
        auto XY=bit[0].run();
        auto X=bit[1].run();
        auto Y=bit[2].run();
        auto Const=bit[3].run();
        vector<T> res(q);
        rep(i,0,q){
            auto [l,d,r,u]=que[i];
            res[i]+=XY[4*i]*l*d;
            res[i]+=X[4*i]*l;
            res[i]+=Y[4*i]*d;
            res[i]+=Const[4*i];

            res[i]-=XY[4*i+1]*l*u;
            res[i]-=X[4*i+1]*l;
            res[i]-=Y[4*i+1]*u;
            res[i]-=Const[4*i+1];

            res[i]-=XY[4*i+2]*r*d;
            res[i]-=X[4*i+2]*r;
            res[i]-=Y[4*i+2]*d;
            res[i]-=Const[4*i+2];

            res[i]+=XY[4*i+3]*r*u;
            res[i]+=X[4*i+3]*r;
            res[i]+=Y[4*i+3]*u;
            res[i]+=Const[4*i+3];
        }
        return res;
    }
};

/**
 * @brief Static Rectangle Add Rectangle Sum
*/

Back to top page