Graph-RangeEdge.cpp

• View this file on GitHub
• Last update: 2025-07-04 15:57:54+09:00

Depends on

• template.cpp

Required by

• test/Graph-RangeEdge.test.cpp

Code

#include "template.cpp"
template <class T>
struct RangeEdgeGraph {
    int n, sz;
    vector<vector<pair<int, T>>> g;
    RangeEdgeGraph(int _n) : n(_n) {
        sz = 1;
        while (sz < n) sz <<= 1;
        g.resize(sz * 3);
        for (int v = 2; v < sz + n; v++) {
            g[v >> 1].push_back({v, 0});
            g[v >= sz ? v : v + sz * 2].push_back({sz * 2 + (v >> 1), 0});
        }
    }
    void add_edge(int l1, int r1, int l2, int r2, T cost) {
        //[l1,r1)->[l2,r2)
        int id = g.size();
        g.push_back({});
        {
            int l = l1, r = r1;
            l += sz, r += sz;
            while (l < r) {
                if (l & 1) {
                    g[(l < sz ? l + sz * 2 : l)].push_back({id, cost});
                    l++;
                }
                if (r & 1) {
                    r--;
                    g[(r < sz ? r + sz * 2 : r)].push_back({id, cost});
                }
                l >>= 1, r >>= 1;
            }
        }
        {
            int l = l2, r = r2;
            l += sz, r += sz;
            while (l < r) {
                if (l & 1) {
                    g[id].push_back({l, 0});
                    l++;
                }
                if (r & 1) {
                    r--;
                    g[id].push_back({r, 0});
                }
                l >>= 1, r >>= 1;
            }
        }
    }
    vector<T> dijkstra(vector<int> start) {
        using P = pair<T, int>;
        vector<T> dp(g.size(), numeric_limits<T>::max());
        priority_queue<P, vector<P>, greater<P>> que;
        for (int s : start) {
            s += sz;
            dp[s] = 0;
            que.push({0, s});
        }
        while (que.size()) {
            auto [d, v] = que.top();
            que.pop();
            if (dp[v] != d) continue;
            for (auto [u, c] : g[v]) {
                if (chmin(dp[u], d + c)) que.push({dp[u], u});
            }
        }
        return vector(dp.begin() + sz, dp.begin() + sz + n);
    }
};

#line 1 "template.cpp"
#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;
template <class T>
using pbds_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template <class T>
using pbds_mset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
using pbds_trie = trie<string, null_type, trie_string_access_traits<>, pat_trie_tag, trie_prefix_search_node_update>;
#define rep(i, n) for (int i = 0; i < n; i++)
#define all(v) v.begin(), v.end()
template <class T, class U>
inline bool chmax(T &a, U b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
template <class T, class U>
inline bool chmin(T &a, U b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
constexpr int INF = 1000000000;
constexpr int64_t llINF = 3000000000000000000;
constexpr double eps = 1e-10;
const double pi = acos(-1);
template <class T>
inline void compress(vector<T> &a) {
    sort(a.begin(), a.end());
    a.erase(unique(a.begin(), a.end()), a.end());
}
struct linear_sieve {
    vector<int> least_factor, prime_list;
    linear_sieve(int n) : least_factor(n + 1, 0) {
        for (int i = 2; i <= n; i++) {
            if (least_factor[i] == 0) {
                least_factor[i] = i;
                prime_list.push_back(i);
            }
            for (int p : prime_list) {
                if (ll(i) * p > n || p > least_factor[i]) break;
                least_factor[i * p] = p;
            }
        }
    }
};
ll extgcd(ll a, ll b, ll &x, ll &y) {
    // ax+by=gcd(|a|,|b|)
    if (a < 0 || b < 0) {
        ll d = extgcd(abs(a), abs(b), x, y);
        if (a < 0) x = -x;
        if (b < 0) y = -y;
        return d;
    }
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    ll d = extgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}
ll modpow(ll a, ll b, ll m) {
    ll res = 1;
    while (b) {
        if (b & 1) {
            res *= a;
            res %= m;
        }
        a *= a;
        a %= m;
        b >>= 1;
    }
    return res;
}
template <typename T, typename U>
inline istream &operator>>(istream &is, pair<T, U> &rhs) {
    return is >> rhs.first >> rhs.second;
}
template <typename T>
inline istream &operator>>(istream &is, vector<T> &v) {
    for (auto &e : v) is >> e;
    return is;
}
template <typename T, typename U>
inline ostream &operator<<(ostream &os, const pair<T, U> &rhs) {
    return os << rhs.first << " " << rhs.second;
}
template <typename T>
inline ostream &operator<<(ostream &os, const vector<T> &v) {
    for (auto itr = v.begin(), end_itr = v.end(); itr != end_itr;) {
        os << *itr;
        if (++itr != end_itr) os << " ";
    }
    return os;
}
#line 2 "Graph-RangeEdge.cpp"
template <class T>
struct RangeEdgeGraph {
    int n, sz;
    vector<vector<pair<int, T>>> g;
    RangeEdgeGraph(int _n) : n(_n) {
        sz = 1;
        while (sz < n) sz <<= 1;
        g.resize(sz * 3);
        for (int v = 2; v < sz + n; v++) {
            g[v >> 1].push_back({v, 0});
            g[v >= sz ? v : v + sz * 2].push_back({sz * 2 + (v >> 1), 0});
        }
    }
    void add_edge(int l1, int r1, int l2, int r2, T cost) {
        //[l1,r1)->[l2,r2)
        int id = g.size();
        g.push_back({});
        {
            int l = l1, r = r1;
            l += sz, r += sz;
            while (l < r) {
                if (l & 1) {
                    g[(l < sz ? l + sz * 2 : l)].push_back({id, cost});
                    l++;
                }
                if (r & 1) {
                    r--;
                    g[(r < sz ? r + sz * 2 : r)].push_back({id, cost});
                }
                l >>= 1, r >>= 1;
            }
        }
        {
            int l = l2, r = r2;
            l += sz, r += sz;
            while (l < r) {
                if (l & 1) {
                    g[id].push_back({l, 0});
                    l++;
                }
                if (r & 1) {
                    r--;
                    g[id].push_back({r, 0});
                }
                l >>= 1, r >>= 1;
            }
        }
    }
    vector<T> dijkstra(vector<int> start) {
        using P = pair<T, int>;
        vector<T> dp(g.size(), numeric_limits<T>::max());
        priority_queue<P, vector<P>, greater<P>> que;
        for (int s : start) {
            s += sz;
            dp[s] = 0;
            que.push({0, s});
        }
        while (que.size()) {
            auto [d, v] = que.top();
            que.pop();
            if (dp[v] != d) continue;
            for (auto [u, c] : g[v]) {
                if (chmin(dp[u], d + c)) que.push({dp[u], u});
            }
        }
        return vector(dp.begin() + sz, dp.begin() + sz + n);
    }
};

Back to top page