library

This documentation is automatically generated by online-judge-tools/verification-helper

---

Project maintained by tko919 Hosted on GitHub Pages — Theme by mattgraham

Area of Union of Rectangles
(DataStructure/unionrect.hpp)

• View this file on GitHub
• Last update: 2024-08-09 08:04:34+09:00
• Include: #include "DataStructure/unionrect.hpp"

Depends on

• Lazy Segment Tree (DataStructure/lazysegtree.hpp)

Verified with

• Verify/LC_area_of_union_of_rectangles.test.cpp

Code

#pragma once
#include "DataStructure/lazysegtree.hpp"


struct UnionInterval{
    struct M{
        ll len,mi,cnt;
    };
    static M f(M a,M b){
        if(a.mi<b.mi)return {a.len+b.len,a.mi,a.cnt};
        else if(a.mi>b.mi)return {a.len+b.len,b.mi,b.cnt};
        else return {a.len+b.len,a.mi,a.cnt+b.cnt};
    }
    static M g(M a,int b){
        return M{a.len,min(INF,a.mi+b),a.cnt};
    }
    static int h(int a,int b){
        return a+b;
    }
    static M m1(){
        return M{0,INF,0};
    }
    static int m2(){return 0;}

    const int n=0;
    LazySegmentTree<M,int,f,g,h,m1,m2> seg;
    UnionInterval(){}
    UnionInterval(vector<int>& xs):n(xs.size()-1){
        vector<M> init(n);
        rep(i,0,n){
            init[i]=M{xs[i+1]-xs[i],0,xs[i+1]-xs[i]};
        }
        seg=LazySegmentTree<M,int,f,g,h,m1,m2>(init);
    }
    void add(int L,int R){
        seg.update(L,R,1);
    }
    void erase(int L,int R){
        seg.update(L,R,-1);
    }
    ll run(){
        auto [len,mi,cnt]=seg.query(0,n);
        if(mi==0)len-=cnt;
        return len;
    }
};

struct UnionRect{
    vector<int> L,R,D,U;
    UnionRect(){}
    void add(int lb,int rb,int db,int ub){
        L.push_back(lb);
        R.push_back(rb);
        D.push_back(db);
        U.push_back(ub);
    }
    ll run(){
        int n=L.size();
        vector<int> xs=L,ys=D;
        xs.insert(xs.end(),ALL(R));
        ys.insert(ys.end(),ALL(U));
        sort(ALL(xs));
        xs.erase(unique(ALL(xs)),xs.end());
        sort(ALL(ys));
        ys.erase(unique(ALL(ys)),ys.end());

        UnionInterval buf=UnionInterval(ys);
        using P=pair<int,int>;
        vector in(xs.size(),vector<P>()),out(xs.size(),vector<P>());
        rep(i,0,n){
            L[i]=lower_bound(ALL(xs),L[i])-xs.begin();
            R[i]=lower_bound(ALL(xs),R[i])-xs.begin();
            D[i]=lower_bound(ALL(ys),D[i])-ys.begin();
            U[i]=lower_bound(ALL(ys),U[i])-ys.begin();
            in[L[i]].push_back({D[i],U[i]});
            out[R[i]].push_back({D[i],U[i]});
        }
        ll ret=0;
        rep(i,0,xs.size()-1){
            for(auto& [d,u]:in[i])buf.add(d,u);
            for(auto& [d,u]:out[i])buf.erase(d,u);
            ret+=buf.run()*(xs[i+1]-xs[i]);
        }
        return ret;
    }
};

/**
 * @brief Area of Union of Rectangles
 */

#line 2 "DataStructure/lazysegtree.hpp"

template <typename M, typename N, M (*f)(M, M), M (*g)(M, N), N (*h)(N, N),
          M (*m1)(), N (*n1)()>
class LazySegmentTree {
    int n, sz, height;
    vector<M> data;
    vector<N> lazy;
    void update(int k) {
        data[k] = f(data[k * 2], data[k * 2 + 1]);
    }
    void apply(int k, N x) {
        data[k] = g(data[k], x);
        if (k < sz)
            lazy[k] = h(lazy[k], x);
    }
    void down(int k) {
        apply(k * 2, lazy[k]);
        apply(k * 2 + 1, lazy[k]);
        lazy[k] = n1();
    }

  public:
    LazySegmentTree(int n = 0) : LazySegmentTree(vector<M>(n, m1())) {}
    LazySegmentTree(const vector<M> &a) : n(SZ(a)) {
        sz = 1, height = 0;
        while (sz < (int)a.size())
            sz <<= 1, height++;
        data.assign(2 * sz, m1());
        lazy.assign(sz, n1());
        rep(i, 0, a.size()) data[sz + i] = a[i];
        for (int i = sz - 1; i; i--)
            update(i);
    }
    M operator[](int k) const {
        k += sz;
        rrep(i, 1, height + 1) down(k >> i);
        return data[k];
    }
    vector<M> get() {
        rep(k, 1, sz) down(k);
        return {data.begin() + sz, data.begin() + sz + n};
    }
    void set(int k, M x) {
        k += sz;
        for (int i = height; i; i--)
            down(k >> i);
        data[k] = x;
        for (int i = 1; i <= height; i++)
            update(k >> i);
    }
    void update(int L, int R, N x) {
        if (L >= R)
            return;
        L += sz, R += sz;
        for (int i = height; i; i--) {
            if (((L >> i) << i) != L)
                down(L >> i);
            if (((R >> i) << i) != R)
                down((R - 1) >> i);
        }
        int lb = L, rb = R;
        while (L < R) {
            if (L & 1)
                apply(L++, x);
            if (R & 1)
                apply(--R, x);
            L >>= 1;
            R >>= 1;
        }
        L = lb, R = rb;
        for (int i = 1; i <= height; i++) {
            if (((L >> i) << i) != L)
                update(L >> i);
            if (((R >> i) << i) != R)
                update((R - 1) >> i);
        }
    }
    M query(int L, int R) {
        if (L >= R)
            return m1();
        L += sz, R += sz;
        for (int i = height; i; i--) {
            if (((L >> i) << i) != L)
                down(L >> i);
            if (((R >> i) << i) != R)
                down((R - 1) >> i);
        }
        M lb = m1(), rb = m1();
        while (L < R) {
            if (L & 1)
                lb = f(lb, data[L++]);
            if (R & 1)
                rb = f(data[--R], rb);
            L >>= 1;
            R >>= 1;
        }
        return f(lb, rb);
    }
    template <class F> int max_right(int L, F ch) {
        if (L == n)
            return n;
        L += sz;
        rrep(i, 1, height + 1) down(L >> i);
        M sum = m1();
        do {
            while (L % 2 == 0)
                L >>= 1;
            if (!ch(f(sum, data[L]))) {
                while (L < sz) {
                    down(L);
                    L <<= 1;
                    if (ch(f(sum, data[L])))
                        sum = f(sum, data[L++]);
                }
                return L - sz;
            }
            sum = f(sum, data[L++]);
        } while ((L & -L) != L);
        return n;
    }
    template <class F> int min_left(int R, F ch) {
        if (R == 0)
            return 0;
        R += sz;
        rrep(i, 1, height + 1) down((R - 1) >> i);
        M sum = m1();
        do {
            R--;
            while (R > 1 and (R & 1))
                R >>= 1;
            if (!ch(f(data[R], sum))) {
                while (R < sz) {
                    down(R);
                    R = (R * 2 + 1);
                    if (ch(f(data[R], sum))) {
                        sum = f(data[R--], sum);
                    }
                }
                return R + 1 - sz;
            }
            sum = f(data[R], sum);
        } while ((R & -R) != R);
        return 0;
    }
};

/**
 * @brief Lazy Segment Tree
 */
#line 3 "DataStructure/unionrect.hpp"

struct UnionInterval{
    struct M{
        ll len,mi,cnt;
    };
    static M f(M a,M b){
        if(a.mi<b.mi)return {a.len+b.len,a.mi,a.cnt};
        else if(a.mi>b.mi)return {a.len+b.len,b.mi,b.cnt};
        else return {a.len+b.len,a.mi,a.cnt+b.cnt};
    }
    static M g(M a,int b){
        return M{a.len,min(INF,a.mi+b),a.cnt};
    }
    static int h(int a,int b){
        return a+b;
    }
    static M m1(){
        return M{0,INF,0};
    }
    static int m2(){return 0;}

    const int n=0;
    LazySegmentTree<M,int,f,g,h,m1,m2> seg;
    UnionInterval(){}
    UnionInterval(vector<int>& xs):n(xs.size()-1){
        vector<M> init(n);
        rep(i,0,n){
            init[i]=M{xs[i+1]-xs[i],0,xs[i+1]-xs[i]};
        }
        seg=LazySegmentTree<M,int,f,g,h,m1,m2>(init);
    }
    void add(int L,int R){
        seg.update(L,R,1);
    }
    void erase(int L,int R){
        seg.update(L,R,-1);
    }
    ll run(){
        auto [len,mi,cnt]=seg.query(0,n);
        if(mi==0)len-=cnt;
        return len;
    }
};

struct UnionRect{
    vector<int> L,R,D,U;
    UnionRect(){}
    void add(int lb,int rb,int db,int ub){
        L.push_back(lb);
        R.push_back(rb);
        D.push_back(db);
        U.push_back(ub);
    }
    ll run(){
        int n=L.size();
        vector<int> xs=L,ys=D;
        xs.insert(xs.end(),ALL(R));
        ys.insert(ys.end(),ALL(U));
        sort(ALL(xs));
        xs.erase(unique(ALL(xs)),xs.end());
        sort(ALL(ys));
        ys.erase(unique(ALL(ys)),ys.end());

        UnionInterval buf=UnionInterval(ys);
        using P=pair<int,int>;
        vector in(xs.size(),vector<P>()),out(xs.size(),vector<P>());
        rep(i,0,n){
            L[i]=lower_bound(ALL(xs),L[i])-xs.begin();
            R[i]=lower_bound(ALL(xs),R[i])-xs.begin();
            D[i]=lower_bound(ALL(ys),D[i])-ys.begin();
            U[i]=lower_bound(ALL(ys),U[i])-ys.begin();
            in[L[i]].push_back({D[i],U[i]});
            out[R[i]].push_back({D[i],U[i]});
        }
        ll ret=0;
        rep(i,0,xs.size()-1){
            for(auto& [d,u]:in[i])buf.add(d,u);
            for(auto& [d,u]:out[i])buf.erase(d,u);
            ret+=buf.run()*(xs[i+1]-xs[i]);
        }
        return ret;
    }
};

/**
 * @brief Area of Union of Rectangles
 */

Back to top page