test/yosupo_Rectangle_Sum.test.cpp

View this file on GitHub
Last update: 2023-04-05 23:10:22+09:00
Problem: https://judge.yosupo.jp/problem/rectangle_sum

Depends on

Code

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

#include "../template.hpp"

#include "../DataStructure/RangeTree.hpp"

signed main(){
    int n,q;cin>>n>>q;
    vector<tuple<int,int,ll>> v;
    rep(i,n){
        int x,y;ll w;cin>>x>>y>>w;
        v.emplace_back(x,y,w);
    }

    RangeTree<int,int,ll> seg(v);


    while(q--){
        int x1,y1,x2,y2;cin>>x1>>y1>>x2>>y2;
        cout<<seg.query(x1,y1,x2,y2)<<"\n";
    }

    return 0;
}

#line 1 "test/yosupo_Rectangle_Sum.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/rectangle_sum"

#line 1 "template.hpp"
#include<bits/stdc++.h>
using namespace std;
#define ALL(x) begin(x),end(x)
#define rep(i,n) for(int i=0;i<(n);i++)
#define debug(v) cout<<#v<<":";for(auto x:v){cout<<x<<' ';}cout<<endl;
#define mod 1000000007
using ll=long long;
const int INF=1000000000;
const ll LINF=1001002003004005006ll;
int dx[]={1,0,-1,0},dy[]={0,1,0,-1};
// ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return true;}return false;}
template<class T>bool chmin(T &a,const T &b){if(b<a){a=b;return true;}return false;}

struct IOSetup{
    IOSetup(){
        cin.tie(0);
        ios::sync_with_stdio(0);
        cout<<fixed<<setprecision(12);
    }
} iosetup;
 
template<typename T>
ostream &operator<<(ostream &os,const vector<T>&v){
    for(int i=0;i<(int)v.size();i++) os<<v[i]<<(i+1==(int)v.size()?"":" ");
    return os;
}
template<typename T>
istream &operator>>(istream &is,vector<T>&v){
    for(T &x:v)is>>x;
    return is;
}

#line 4 "test/yosupo_Rectangle_Sum.test.cpp"

#line 1 "DataStructure/RangeTree.hpp"
// Range Tree (Weighted)
template<typename Tx,typename Ty,typename VAL=int>
struct RangeTree{
    private:
    vector<vector<Ty>> seg;
    vector<vector<VAL>> sum;
    vector<Tx> x;
    int sz;

    void build(vector<tuple<Tx,Ty,VAL>> &v){
        sort(begin(v),end(v));
        for(int i=0;i<(int)v.size();i++) x.push_back(get<0>(v[i]));
        x.erase(unique(begin(x),end(x)),end(x));
        sz=1;
        while((int)x.size()>sz) sz<<=1;
        while((int)x.size()<sz) x.push_back(numeric_limits<Tx>::max()/2);
        seg.resize(sz*2);
        sum.resize(sz*2);
        int idx=0;
        for(auto [x_,y_,val]:v){
            if(x[idx]!=x_) idx++;
            seg[idx+sz].push_back(y_);
            sum[idx+sz].push_back(val);
        }
        for(int i=sz-1;i>0;i--){
            int l=0,r=0;
            while(l<(int)seg[2*i].size() or r<(int)seg[2*i+1].size()){
                bool f;
                if(r>=(int)seg[2*i+1].size()) f=true;
                else if(l>=(int)seg[2*i].size()) f=false;
                else if(seg[2*i][l]<seg[2*i+1][r]) f=true;
                else f=false;
                if(f){
                    seg[i].push_back(seg[2*i][l]);
                    sum[i].push_back(sum[2*i][l]);
                    l++;
                }else{
                    seg[i].push_back(seg[2*i+1][r]);
                    sum[i].push_back(sum[2*i+1][r]);
                    r++;
                }
            }
        }
        for(int i=1;i<2*sz;i++){
            vector<VAL> replace(1,0);
            for(auto val:sum[i]) replace.push_back(replace.back()+val);
            swap(sum[i],replace);
        }
    }
    
    public:
    RangeTree(vector<pair<Tx,Ty>> a){
        vector<tuple<Tx,Ty,VAL>> v;
        for(auto p:a) v.emplace_back(p.first,p.second,1);
        build(v);
    }
    RangeTree(vector<tuple<Tx,Ty,VAL>> a){
        build(a);
    }
    // sum : [x1,x2),[y1,y2)
    VAL query(Tx x1,Ty y1,Tx x2,Ty y2){
        int l=lower_bound(begin(x),end(x),x1)-begin(x),r=lower_bound(begin(x),end(x),x2)-begin(x);
        l+=sz,r+=sz;
        VAL ret=0;
        for(;l<r;l>>=1,r>>=1){
            if(l&1){
                int hi=lower_bound(begin(seg[l]),end(seg[l]),y2)-begin(seg[l]);
                int lw=lower_bound(begin(seg[l]),end(seg[l]),y1)-begin(seg[l]);
                ret+=sum[l][hi]-sum[l][lw];
                l++;
            }
            if(r&1){
                r--;
                int hi=lower_bound(begin(seg[r]),end(seg[r]),y2)-begin(seg[r]);
                int lw=lower_bound(begin(seg[r]),end(seg[r]),y1)-begin(seg[r]);
                ret+=sum[r][hi]-sum[r][lw];
            }
        }
        return ret;
    }
};
#line 6 "test/yosupo_Rectangle_Sum.test.cpp"

signed main(){
    int n,q;cin>>n>>q;
    vector<tuple<int,int,ll>> v;
    rep(i,n){
        int x,y;ll w;cin>>x>>y>>w;
        v.emplace_back(x,y,w);
    }

    RangeTree<int,int,ll> seg(v);


    while(q--){
        int x1,y1,x2,y2;cin>>x1>>y1>>x2>>y2;
        cout<<seg.query(x1,y1,x2,y2)<<"\n";
    }

    return 0;
}