src/test/yosupo_point_add_rectangle_sum.fen.cpp

View this file on GitHub
Last update: 2026-03-17 19:58:42+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 "../structure/fen2d.hpp"

int main(){
    int N,Q;
    cin>>N>>Q;
    vector<array<int,5>> qu(N+Q);
    Fen2D<int,long> f2d;
    rep(i,N){
        int x,y,w;
        cin>>x>>y>>w;
        qu[i]={0,x,y,w};
        f2d.add_point(x,y);
    }
    rep(i,Q){
        int t;
        cin>>t;
        if(t==0){
            int x,y,w;
            cin>>x>>y>>w;
            qu[i+N]={0,x,y,w};
            f2d.add_point(x,y);
        }
        else {
            int l,d,r,u;
            cin>>l>>d>>r>>u;
            qu[i+N]={1,l,d,r,u};
        }
    }
    f2d.build();
    for(auto a: qu){
        if(a[0]==0){
            f2d.add(a[1],a[2],a[3]);
        }
        else {
            cout<<f2d.sum(a[1],a[3],a[2],a[4])<<"\n";
        }
    }
}

#line 1 "src/test/yosupo_point_add_rectangle_sum.fen.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/point_add_rectangle_sum"
#line 2 "src/template.hpp"
#include <bits/stdc++.h>
using namespace std;
#define si(a) (long)a.size()
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define rep(i,n) for(int i=0;i<(int)(n);++i)
template<typename S,typename F> bool chmin(S&a,F b){return b<a?(a=b,1):0;}
template<typename S,typename F> bool chmax(S&a,F b){return b>a?(a=b,1):0;}
bool _=(ios::sync_with_stdio(0),cin.tie(0),cout<<fixed<<setprecision(16),0);
#line 3 "src/structure/fenwick_tree.hpp"

template<class T> struct fenwick_tree {
    vector<T> a;
    fenwick_tree():a(1,0){}
    fenwick_tree(int n):a(n+1,0){}
    void add(int i,T x){
        for(i++;i<si(a);i+=i&-i) a[i]+=x;
    }
    T sum(int r){
        T s=0;
        for(;r;r-=r& -r) s+=a[r];
        return s;
    }
    T sum(int l,int r){return sum(r)-sum(l);}

    int lower_bound(T w){
        if(w<=0) return 0;
        int x=0,k=1;
        while(k<si(a))k<<=1;
        for(;k;k>>=1){
            if(x+k<si(a)&&a[x+k]<w){
                w-=a[x+k];
                x+=k;
            }
        }
        return x+1;
    }
};
#line 2 "src/structure/fen2d.hpp"

template<typename K,typename T>
struct Fen2D {
    int n;
    vector<pair<K,K>> ps;
    vector<K> xz;
    vector<vector<K>> ys;
    vector<fenwick_tree<T>> bit;

    void add_point(K x,K y){
        ps.emplace_back(x,y);
    }
    void build(){
        xz.resize(si(ps));
        rep(i,si(ps)) xz[i]=ps[i].fi;
        sort(all(xz));
        xz.erase(unique(all(xz)),xz.end());
        n=si(xz);
        bit.resize(n+1);
        ys.resize(n+1);
        sort(all(ps));
        for(int i=0,j=0;i<n;i++) for(;j<si(ps)&&ps[j].fi<=xz[i];ps[j++].fi=i);
        for(auto &[x,y]: ps) for(int i=x+1;i<=n;i+=i& -i) ys[i].push_back(y);
        for(int i=1;i<=n;i++){
            sort(all(ys[i]));
            ys[i].erase(unique(all(ys[i])),ys[i].end());
            bit[i]=fenwick_tree<T>(si(ys[i]));
        }
    }
    void add(K x,K y,T w){
        x=lower_bound(all(xz),x)-xz.begin();
        for(int i=x+1;i<=n;i+=i& -i){
            int j=lower_bound(all(ys[i]),y)-ys[i].begin();
            bit[i].add(j,w);
        }
    }
    T sum(K x,K y){
        x=lower_bound(all(xz),x)-xz.begin();
        T s=0;
        for(;x;x-=x& -x){
            int j=lower_bound(ys[x].begin(),ys[x].end(),y)-ys[x].begin();
            s+=bit[x].sum(j);
        }
        return s;
    }
    T sum(K l,K r,K d,K u){
        return sum(r,u)-sum(l,u)-sum(r,d)+sum(l,d);
    }
};
#line 3 "src/test/yosupo_point_add_rectangle_sum.fen.cpp"

int main(){
    int N,Q;
    cin>>N>>Q;
    vector<array<int,5>> qu(N+Q);
    Fen2D<int,long> f2d;
    rep(i,N){
        int x,y,w;
        cin>>x>>y>>w;
        qu[i]={0,x,y,w};
        f2d.add_point(x,y);
    }
    rep(i,Q){
        int t;
        cin>>t;
        if(t==0){
            int x,y,w;
            cin>>x>>y>>w;
            qu[i+N]={0,x,y,w};
            f2d.add_point(x,y);
        }
        else {
            int l,d,r,u;
            cin>>l>>d>>r>>u;
            qu[i+N]={1,l,d,r,u};
        }
    }
    f2d.build();
    for(auto a: qu){
        if(a[0]==0){
            f2d.add(a[1],a[2],a[3]);
        }
        else {
            cout<<f2d.sum(a[1],a[3],a[2],a[4])<<"\n";
        }
    }
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	example_00	AC	4 ms	4 MB
g++	many_points_00	AC	1760 ms	47 MB
g++	many_queries_00	AC	1892 ms	32 MB
g++	max_random_00	AC	1907 ms	40 MB
g++	max_random_01	AC	1924 ms	40 MB
g++	power_of_2_00	AC	1187 ms	20 MB
g++	power_of_2_01	AC	1181 ms	20 MB
g++	random_00	AC	723 ms	17 MB
g++	random_01	AC	678 ms	22 MB
g++	random_02	AC	940 ms	24 MB
g++	small_00	AC	7 ms	4 MB
g++	small_01	AC	5 ms	4 MB
g++	small_02	AC	5 ms	4 MB
g++	small_03	AC	5 ms	4 MB
g++	small_04	AC	8 ms	4 MB
g++	xy_concentrate_00	AC	901 ms	16 MB
g++	xy_concentrate_01	AC	903 ms	16 MB
g++	xy_concentrate_02	AC	900 ms	16 MB