test/binary-indexed-tree/BinaryIndexedTreeOffline2D-2.test.cpp

View this file on GitHub
Last update: 2023-05-31 01:48:55+09:00
Problem: https://judge.yosupo.jp/problem/point_add_rectangle_sum

Depends on

Code

#define PROBLEM "https://judge.yosupo.jp/problem/point_add_rectangle_sum"

#include <vector>
#include <iostream>
#include <stack>
#include <algorithm>
using namespace std;
#include "../../lib/99-operator/abel/AbelPrefixSumPointAdd.cpp"
#include "../../lib/11-binary-indexed-tree/BinaryIndexedTreeOffline2D.cpp"

int main(void){
    int N,Q;
    scanf("%d %d",&N,&Q);
    vector<long long> X(N+Q,0),Y(N+Q,0),W(N+Q,0);
    vector<int> A(Q),L(Q),D(Q),R(Q),U(Q);
    for(int i=0;i<N;++i) scanf("%d %d %d",&X[i],&Y[i],&W[i]);
    for(int i=0;i<Q;++i) {
        scanf("%d",&A[i]);
        if(A[i]==0) scanf("%d %d %d",&X[i+N],&Y[i+N],&W[i+N]);
        else scanf("%d %d %d %d",&L[i],&D[i],&R[i],&U[i]);
    }
    BinaryIndexedTreeOffline2D<AbelPrefixSumPointAdd<long long>> bit(X,Y);
    for(int i=0;i<N;++i) bit.operate(X[i],Y[i],W[i]);
    for(int i=0;i<Q;++i) {
        if(A[i]==0) bit.operate(X[i+N],Y[i+N],W[i+N]);
        else printf("%lld\n",bit.fold(L[i],R[i],D[i],U[i]));
    }
    return 0; 
}

#line 1 "test/binary-indexed-tree/BinaryIndexedTreeOffline2D-2.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/point_add_rectangle_sum"

#include <vector>
#include <iostream>
#include <stack>
#include <algorithm>
using namespace std;
#line 1 "lib/99-operator/abel/AbelPrefixSumPointAdd.cpp"
/*
 * @title AbelPrefixSumPointAdd
 * @docs md/operator/abel/AbelPrefixSumPointAdd.md
 */
template<class T> struct AbelPrefixSumPointAdd {
    using TypeNode = T;
    inline static constexpr TypeNode unit_node = 0;
    inline static constexpr TypeNode func_fold(const TypeNode& l,const TypeNode& r){return l+r;}
    inline static constexpr TypeNode func_fold_inv(const TypeNode& l,const TypeNode& r){return l-r;}
};
#line 1 "lib/11-binary-indexed-tree/BinaryIndexedTreeOffline2D.cpp"
/*
 * @title BinaryIndexedTreeOffline2D - オフライン2次元BIT
 * @docs md/binary-indexed-tree/BinaryIndexedTreeOffline2D.md
 */
template<class Abel> class BinaryIndexedTreeOffline2D {
    using TypeNode = typename Abel::TypeNode;
    using i64 = long long;

    class InternalBinaryIndexedTree {
        size_t length;
        vector<TypeNode> node;
    public:
        InternalBinaryIndexedTree() {}
        InternalBinaryIndexedTree(const size_t num) {
            for (length = 1; length < num; length *= 2);
            node.resize(length+1, Abel::unit_node);
        }
        void operate(size_t idx, TypeNode var) {
            for (++idx; idx <= length; idx += idx & -idx) node[idx] = Abel::func_fold(node[idx],var);
        }
        TypeNode fold(size_t idx) {
            TypeNode ret = Abel::unit_node;
            for (idx = min(length,idx); idx > 0; idx -= idx & -idx) ret = Abel::func_fold(ret,node[idx]);
            return ret;
        }
    };
    size_t length;
    vector<InternalBinaryIndexedTree> node;
    vector<i64> ox;
    vector<vector<i64>> oy;

public:

    BinaryIndexedTreeOffline2D(const vector<i64>& operator_x,const vector<i64>& operator_y):ox(operator_x) {
        sort(ox.begin(),ox.end());
        ox.erase(unique(ox.begin(),ox.end()),ox.end());
        size_t num = ox.size();
        for (length = 1; length < num; length *= 2);
        node.resize(length+1);
        oy.resize(length+1);
        int n = operator_x.size();
        for(int i=0;i<n;++i) {
            size_t x = (lower_bound(ox.begin(),ox.end(),operator_x[i])-ox.begin());
            for (++x;x<=length; x += x & -x) {
                oy[x].push_back(operator_y[i]);
            }
        }
        for(int i=0;i<length+1;++i) {
            sort(oy[i].begin(),oy[i].end());
            oy[i].erase(unique(oy[i].begin(),oy[i].end()),oy[i].end());
            node[i]=InternalBinaryIndexedTree(oy[i].size());
        }
    }

    //[l,l+1),[d,d+1) operate
    void operate(i64 l, i64 d, TypeNode var) {
        size_t x = (lower_bound(ox.begin(),ox.end(),l)-ox.begin());
        for (++x; x <= length; x += x & -x) {
            size_t y = (lower_bound(oy[x].begin(),oy[x].end(),d)-oy[x].begin());
            node[x].operate(y,var);
        }
    }

    //[0,r),[0,u) fold
    TypeNode fold(i64 l, i64 u) {
        TypeNode ret = Abel::unit_node;
        size_t x = (lower_bound(ox.begin(),ox.end(),l)-ox.begin());
        for (x = min(length,x); x > 0; x -= x & -x) {
            size_t y = (lower_bound(oy[x].begin(),oy[x].end(),u)-oy[x].begin());
            ret = Abel::func_fold(ret,node[x].fold(y));
        }
        return ret;
    }

    // [l,r),[d,u) fold
    TypeNode fold(i64 l, i64 r, i64 d, i64 u) {
        return Abel::func_fold_inv(Abel::func_fold(fold(r,u),fold(l,d)),Abel::func_fold(fold(r,d),fold(l,u)));
    }
};
#line 10 "test/binary-indexed-tree/BinaryIndexedTreeOffline2D-2.test.cpp"

int main(void){
    int N,Q;
    scanf("%d %d",&N,&Q);
    vector<long long> X(N+Q,0),Y(N+Q,0),W(N+Q,0);
    vector<int> A(Q),L(Q),D(Q),R(Q),U(Q);
    for(int i=0;i<N;++i) scanf("%d %d %d",&X[i],&Y[i],&W[i]);
    for(int i=0;i<Q;++i) {
        scanf("%d",&A[i]);
        if(A[i]==0) scanf("%d %d %d",&X[i+N],&Y[i+N],&W[i+N]);
        else scanf("%d %d %d %d",&L[i],&D[i],&R[i],&U[i]);
    }
    BinaryIndexedTreeOffline2D<AbelPrefixSumPointAdd<long long>> bit(X,Y);
    for(int i=0;i<N;++i) bit.operate(X[i],Y[i],W[i]);
    for(int i=0;i<Q;++i) {
        if(A[i]==0) bit.operate(X[i+N],Y[i+N],W[i+N]);
        else printf("%lld\n",bit.fold(L[i],R[i],D[i],U[i]));
    }
    return 0; 
}