verify/yosupo/data-structure/area_of_union_of_rectangles.test.cpp

• View this file on GitHub
• Last update: 2024-10-31 23:18:18+07:00
• Problem: https://judge.yosupo.jp/problem/area_of_union_of_rectangles

Depends on

• data-structure/segment-tree/dynamic-segment-tree.hpp
• group/monoid-action/min-count-add.hpp
• group/monoid/add.hpp
• group/monoid/min-count.hpp
• template.hpp

Code

#define PROBLEM "https://judge.yosupo.jp/problem/area_of_union_of_rectangles"
#include "template.hpp"
#include "data-structure/segment-tree/dynamic-segment-tree.hpp"
#include "group/monoid-action/min-count-add.hpp"

int main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    int n;
    cin >> n;
    map<int,vector<tuple<int,int,int>>> qr;
    for(int i=0;i<n;++i){
        int lx,ly,rx,ry;
        cin >> lx >> ly >> rx >> ry;
        ry--;
        qr[lx].emplace_back(ly,ry,1);
        qr[rx].emplace_back(ly,ry,-1);
    }
    const int X=1e9;
    DynamicSegmentTree<MinCountAddAction<int>> s(0,X-1,[](int l,int r){
        return make_pair(0,r-l+1);
    });
    ll ans=0,pre=0;
    for(auto &[x,v]:qr){
        auto [val,cnt]=s.query(0,X);
        if(val>0)cnt=0;
        ans+=(X-cnt)*(x-pre);
        for(auto &[l,r,d]:v)s.update(l,r,d);
        pre=x;
    }
    cout << ans;
}

#line 1 "verify/yosupo/data-structure/area_of_union_of_rectangles.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/area_of_union_of_rectangles"
#line 1 "template.hpp"
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

using ll = long long;
using db = long double;
using vi = vector<int>;
using vl = vector<ll>;
using vd = vector<db>;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using pdd = pair<db,db>;
const int INF=INT_MAX/2;
const int MOD=998244353;
const int MOD2=1000000007;
const ll LINF=LLONG_MAX/2;
const db DINF=numeric_limits<db>::infinity();
const db EPS=1e-9;
const db PI=acos(db(-1));

template<class T>
using ordered_set = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
template<class T>
using ordered_multiset = tree<T,null_type,less_equal<T>,rb_tree_tag,tree_order_statistics_node_update>;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 rng64(chrono::steady_clock::now().time_since_epoch().count());
#line 2 "data-structure/segment-tree/dynamic-segment-tree.hpp"

/**
 * Author: Teetat T.
 * Date: 2024-01-15
 * Description: Dynamic Segment Tree
 */

template<class MonoidAction>
struct DynamicSegmentTree{
    using InfoMonoid = typename MonoidAction::InfoMonoid;
    using TagMonoid = typename MonoidAction::TagMonoid;
    using Info = typename MonoidAction::Info;
    using Tag = typename MonoidAction::Tag;
    struct Node;
    using Ptr = Node*;
    struct Node{
        Info val;
        Tag lz;
        Ptr l,r;
        Node(Info v):val(v),lz(TagMonoid::unit()),l(nullptr),r(nullptr){}
        Node(Info v,Tag t):val(v),lz(t),l(nullptr),r(nullptr){}
    };
    ll lb,ub;
    Ptr rt;
    function<Info(ll,ll)> create;
    DynamicSegmentTree(){init(0,0);}
    DynamicSegmentTree(ll n){init(0,n-1);}
    DynamicSegmentTree(ll lb,ll ub){init(lb,ub);}
    DynamicSegmentTree(ll lb,ll ub,function<Info(ll,ll)> create){init(lb,ub,create);}
    void init(ll _lb,ll _ub,function<Info(ll,ll)> _create=[](ll l,ll r){return InfoMonoid::unit();}){
        lb=_lb,ub=_ub;
        create=_create;
        rt=new Node(create(lb,ub));
    }
    Info val(Ptr t){
        return t?t->val:InfoMonoid::unit();
    }
    void pull(Ptr &t){
        t->val=InfoMonoid::op(val(t->l),val(t->r));
    }
    void apply(Ptr &t,const Tag &v,ll l,ll r){
        if(!t)t=new Node(create(l,r));
        t->val=MonoidAction::op(t->val,v);
        t->lz=TagMonoid::op(t->lz,v);
    }
    void push(Ptr &t,ll l,ll m,ll r){
        apply(t->l,t->lz,l,m);
        apply(t->r,t->lz,m+1,r);
        t->lz=TagMonoid::unit();
    }
    void modify(ll l,ll r,Ptr &t,ll x,const Info &v){
        if(x<l||r<x)return;
        if(l==r)return void(t->val=v);
        ll m=l+(r-l)/2;
        push(t,l,m,r);
        modify(l,m,t->l,x,v);
        modify(m+1,r,t->r,x,v);
        pull(t);
    }
    void modify(ll x,const Info &v){
        modify(lb,ub,rt,x,v);
    }
    void update(ll l,ll r,Ptr &t,ll x,ll y,const Tag &v){
        if(y<l||r<x)return;
        if(x<=l&&r<=y)return apply(t,v,l,r);
        ll m=l+(r-l)/2;
        push(t,l,m,r);
        update(l,m,t->l,x,y,v);
        update(m+1,r,t->r,x,y,v);
        pull(t);
    }
    void update(ll x,ll y,const Tag &v){
        update(lb,ub,rt,x,y,v);
    }
    Info query(ll l,ll r,Ptr &t,ll x,ll y){
        if(y<l||r<x)return InfoMonoid::unit();
        if(x<=l&&r<=y)return t->val;
        ll m=l+(r-l)/2;
        push(t,l,m,r);
        return InfoMonoid::op(query(l,m,t->l,x,y),query(m+1,r,t->r,x,y));
    }
    Info query(ll x,ll y){
        return query(lb,ub,rt,x,y);
    }
    template<class F>
    ll findfirst(ll l,ll r,Ptr t,ll x,ll y,const F &f){
        if(y<l||r<x||!f(t->val))return -1;
        if(l==r)return l;
        ll m=l+(r-l)/2;
        push(t,l,m,r);
        ll res=findfirst(l,m,t->l,x,y,f);
        if(res==-1)res=findfirst(m+1,r,t->r,x,y,f);
        return res;
    }
    template<class F>
    ll findfirst(ll x,ll y,const F &f){
        return findfirst(lb,ub,rt,x,y,f);
    }
    template<class F>
    ll findlast(ll l,ll r,Ptr t,ll x,ll y,const F &f){
        if(y<l||r<x||!t||!f(t->val))return -1;
        if(l==r)return l;
        ll m=l+(r-l)/2;
        push(t,l,m,r);
        ll res=findlast(m+1,r,t->r,x,y,f);
        if(res==-1)res=findlast(l,m,t->l,x,y,f);
        return res;
    }
    template<class F>
    ll findlast(ll x,ll y,const F &f){
        return findlast(lb,ub,rt,x,y,f);
    }
};

#line 2 "group/monoid/add.hpp"

/**
 * Author: Teetat T.
 * Date: 2024-04-14
 * Description: Add Monoid class.
 */

template<class T>
struct AddMonoid{
    using value_type = T;
    static constexpr T op(const T &x,const T &y){return x+y;}
    static constexpr T inverse(const T &x){return -x;}
    static constexpr T unit(){return T(0);}
};

#line 2 "group/monoid/min-count.hpp"

/**
 * Author: Teetat T.
 * Date: 2024-04-14
 * Description: Min & Count Monoid class.
 */

template<class T>
struct MinCountMonoid{
    using P = pair<T,int>;
    using value_type = P;
    static constexpr P op(const P &x,const P &y){
        if(x.first<y.first)return x;
        if(y.first<x.first)return y;
        return P(x.first,x.second+y.second);
    }
    static constexpr P unit(){return P(numeric_limits<T>::max(),0);}
    static constexpr P make(const T &x){return P(x,1);}
};

#line 4 "group/monoid-action/min-count-add.hpp"

/**
 * Author: Teetat T.
 * Date: 2024-04-14
 * Description: Add to Min & Count Action class.
 */

template<class T>
struct MinCountAddAction{
    using InfoMonoid = MinCountMonoid<T>;
    using TagMonoid = AddMonoid<T>;
    using Info = typename InfoMonoid::value_type;
    using Tag = typename TagMonoid::value_type;
    static constexpr Info op(const Info &a,const Tag &b){
        if(a.first==InfoMonoid::unit().first)return a;
        return Info(a.first+b,a.second);
    }
};

#line 5 "verify/yosupo/data-structure/area_of_union_of_rectangles.test.cpp"

int main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    int n;
    cin >> n;
    map<int,vector<tuple<int,int,int>>> qr;
    for(int i=0;i<n;++i){
        int lx,ly,rx,ry;
        cin >> lx >> ly >> rx >> ry;
        ry--;
        qr[lx].emplace_back(ly,ry,1);
        qr[rx].emplace_back(ly,ry,-1);
    }
    const int X=1e9;
    DynamicSegmentTree<MinCountAddAction<int>> s(0,X-1,[](int l,int r){
        return make_pair(0,r-l+1);
    });
    ll ans=0,pre=0;
    for(auto &[x,v]:qr){
        auto [val,cnt]=s.query(0,X);
        if(val>0)cnt=0;
        ans+=(X-cnt)*(x-pre);
        for(auto &[l,r,d]:v)s.update(l,r,d);
        pre=x;
    }
    cout << ans;
}

Back to top page