#788864 (C++17) No.399 動的な領主

提出ソース
結果

問題	No.399 動的な領主
ユーザー	cutmdo
提出日時	2022-08-15 20:52:38
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	656 ms / 2,000 ms
コード長	12,658 bytes
コンパイル時間	4,917 ms
コンパイル使用メモリ	301,324 KB
実行使用メモリ	93,624 KB
最終ジャッジ日時	2024-04-27 04:10:33
合計ジャッジ時間	11,701 ms
ジャッジサーバーID （参考情報）	judge2 / judge1
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,812 KB
testcase_01	AC	1 ms 6,940 KB
testcase_02	AC	2 ms 6,940 KB
testcase_03	AC	2 ms 6,944 KB
testcase_04	AC	4 ms 6,940 KB
testcase_05	AC	35 ms 9,600 KB
testcase_06	AC	640 ms 66,996 KB
testcase_07	AC	649 ms 66,996 KB
testcase_08	AC	557 ms 58,040 KB
testcase_09	AC	606 ms 58,168 KB
testcase_10	AC	4 ms 6,940 KB
testcase_11	AC	21 ms 6,940 KB
testcase_12	AC	349 ms 23,348 KB
testcase_13	AC	368 ms 23,092 KB
testcase_14	AC	272 ms 93,624 KB
testcase_15	AC	322 ms 93,624 KB
testcase_16	AC	270 ms 58,540 KB
testcase_17	AC	651 ms 58,040 KB
testcase_18	AC	656 ms 58,172 KB
権限があれば一括ダウンロードができます
ソースコード

raw source code
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,avx512f")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <iostream>
#include <iomanip>
#include <string>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <stack>
#include <queue>
#include <bitset>
#include <numeric>
#include <cassert>
#include <memory>
#include <random>
#include <functional>
#include <complex>
#include <immintrin.h>
#include <stdexcept>
#ifdef DEBUG
#include "./CompetitiveProgrammingCpp/debug.hpp"
#include "./CompetitiveProgrammingCpp/Timer.hpp"
#include "./CompetitiveProgrammingCpp/sample.hpp"
#else
#define dump(...)
template<class T>constexpr inline auto d_val(T a, T b) { return a; }
#endif

/* macro */
#define FOR(i, b, e) for(ll i = (ll)(b); i < (ll)(e); ++i)
#define RFOR(i, b, e) for(ll i = (ll)((e)-1); i >= (ll)(b); --i)
#define REP(i, n) FOR(i, 0, (n))
#define RREP(i, n) RFOR(i, 0, (n))
#define REPC(x,c) for(const auto& x:(c))
#define REPI2(it,b,e) for(auto it = (b); it != (e); ++it)
#define REPI(it,c) REPI2(it, (c).begin(), (c).end())
#define RREPI(it,c) REPI2(it, (c).rbegin(), (c).rend())
#define REPI_ERACE2(it, b, e) for(auto it = (b); it != (e);)
#define REPI_ERACE(it, c) REPI_ERACE2(it, (c).begin(), (c).end())
#define ALL(x) (x).begin(),(x).end()
#define cauto const auto&
/* macro func */
template<class T>
inline auto sort(T& t) { std::sort(ALL(t)); }
template<class T>
inline auto rsort(T& t) { std::sort((t).rbegin(), (t).rend()); }
template<class T>
inline auto unique(T& t) { (t).erase(unique((t).begin(), (t).end()), (t).end()); }
template<class T, class S>
inline auto chmax(T& t, const S& s) { if(s > t) { t = s; return true; } return false; }
template<class T, class S>
inline auto chmin(T& t, const S& s) { if(s < t) { t = s; return true; } return false; }
inline auto BR() { std::cout << "\n"; }

/* type define */
using ll = long long;
using VS = std::vector<std::string>;
using VL = std::vector<long long>;
using VVL = std::vector<VL>;
using VVVL = std::vector<VVL>;
using VVVVL = std::vector<VVVL>;
using VVVVVL = std::vector<VVVVL>;
using VD = std::vector<double>;
template<class T>
using V = std::vector<T>;
template<class T = ll, class U = T>
using P = std::pair<T, U>;
using PAIR = P<ll>;

/* using std */
using std::cout;
constexpr char endl = '\n';
using std::cin;
using std::pair;
using std::string;
using std::stack;
using std::queue;
using std::deque;
using std::vector;
using std::list;
using std::map;
using std::unordered_map;
using std::multimap;
using std::unordered_multimap;
using std::set;
using std::unordered_set;
using std::unordered_multiset;
using std::multiset;
using std::bitset;
using std::priority_queue;

/* Initial processing  */
struct Preprocessing { Preprocessing() { std::cin.tie(0); std::ios::sync_with_stdio(0); }; }_Preprocessing;

/* Remove the source of the bug */
auto pow(signed, signed) { assert(false); }

/* define hash */
namespace std {
template <>	class hash<std::pair<ll, ll>> { public:	size_t operator()(const std::pair<ll, ll>& x) const { return hash<ll>()(1000000000 * x.first + x.second); } };
}

/* input */
template<class T> std::istream& operator >> (std::istream& is, vector<T>& vec) { for(T& x : vec) is >> x; return is; }

/* constant value */
// constexpr ll MOD = 1000000007;
constexpr ll MOD = 998244353;

//=============================================================================================


class SegmentTree {
private:
    const ll m_size;
    const ll m_initialValue;
    std::vector<ll> m_node;
    std::vector<ll> m_lazy;

    ll calcSize(ll n) {
        ll size = 1;
        while(size < n) {
            size *= 2;
        }
        return size;
    }
public:
    SegmentTree(ll n, ll val) :
        m_size(calcSize(n)),
        m_initialValue(val),
        m_node(m_size * 2 - 1, m_initialValue),
        m_lazy(m_size * 2 - 1, m_initialValue) {
    }

    void add(ll a, ll b, ll x) { add(a, b + 1, x, 0, 0, m_size); }
    void add(ll a, ll b, ll x, ll k, ll l, ll r) {
        eval(k);
        if(r <= a || b <= l) { return; }
        if(a <= l && r <= b) {
            m_lazy[k] += x * (r - l);
            eval(k);
            return;
        }
        add(a, b, x, 2 * k + 1, l, (l + r) / 2);
        add(a, b, x, 2 * k + 2, (l + r) / 2, r);
        m_node[k] = m_node[2 * k + 1] + m_node[2 * k + 2];
    }
    void eval(ll k) {
        if(m_lazy[k] == m_initialValue) { return; }
        m_node[k] += m_lazy[k];
        if(k < m_size - 1) {
            m_lazy[2 * k + 1] += m_lazy[k] / 2;
            m_lazy[2 * k + 2] += m_lazy[k] / 2;
        }
        m_lazy[k] = m_initialValue;
    }
    ll query(ll a, ll b) { return query(a, b + 1, 0, 0, m_size); }
    ll query(ll a, ll b, ll k, ll l, ll r) {
        if(r <= a || b <= l) { return m_initialValue; }
        eval(k);
        if(a <= l && r <= b) { return m_node[k]; }
        return
            query(a, b, 2 * k + 1, l, (l + r) / 2) +
            query(a, b, 2 * k + 2, (l + r) / 2, r);
    }
};

class HLD {

    using node_t = ll;
    using Graph_f = std::unordered_multimap<node_t, node_t>;
    using Graph = std::unordered_map<node_t, std::deque<node_t>>;

    const node_t m_n;
    const Graph m_tree;
    const std::vector<node_t> m_height;
    const std::vector<std::pair<node_t, node_t>> m_root_par;
    const std::vector<node_t> m_ids;
    const std::vector<node_t> m_order;
    const std::vector<node_t> m_edge_ids;

    static auto constructGraph(node_t n, const Graph_f& tree) {
        std::deque<std::pair<node_t, node_t>> order;
        std::vector<node_t> used(n);
        std::stack<std::pair<node_t, node_t>> stk;
        stk.emplace(0, -1); used[0] = true;
        while(!stk.empty()) {
            auto [f, p] = stk.top();
            order.emplace_front(f, p);
            stk.pop();
            auto range = tree.equal_range(f);
            for(auto itr = range.first; itr != range.second; ++itr) {
                auto t = itr->second;
                if(!used[t]) {
                    used[t] = true;
                    stk.emplace(t, f);
                }
            }
        }

        std::vector<node_t> size(n, 1);
        Graph hld_tree;
        for(const auto& [f, p] : order) {
            auto range = tree.equal_range(f);
            node_t size_sum = 1;
            node_t size_max = 0;
            std::deque<node_t> to_list;
            for(auto itr = range.first; itr != range.second; ++itr) {
                auto t = itr->second;
                if(t == p) { continue; }
                if(size[t] > size_max) {
                    size_max = size[t];
                    to_list.emplace_back(t);
                } else {
                    to_list.emplace_front(t);
                }
                size_sum += size[t];
            }
            if(!to_list.empty()) {
                hld_tree.emplace(f, to_list);
            }
            size[f] = size_sum;
        }
        return hld_tree;
    }
    static auto constructRootPar(node_t n, const Graph& tree) {
        std::vector<std::pair<node_t, node_t>> root_par(n);
        std::stack<std::tuple<node_t, node_t, node_t>> stk;
        stk.emplace(0, 0, -1);
        while(!stk.empty()) {
            auto [f, root, par] = stk.top();
            stk.pop();

            if(tree.find(f) == tree.end()) { root_par[f] = {root,par}; continue; }
            auto itr = tree.at(f).rbegin();
            stk.emplace(*itr, root, par);
            root_par[f] = {root,par};
            for(++itr; itr != tree.at(f).rend(); ++itr) {
                stk.emplace(*itr, *itr, f);
            }
        }
        return root_par;
    }
    static auto constructHeight(node_t n, const Graph& tree) {
        std::vector<node_t> height(n);
        std::queue<node_t> q;
        q.emplace(0);
        while(!q.empty()) {
            auto f = q.front();
            q.pop();
            if(tree.find(f) == tree.end()) { continue; }
            for(const auto& t : tree.at(f)) {
                height[t] = height[f] + 1;
                q.emplace(t);
            }
        }
        return height;
    }

    auto constructIds() const {
        std::vector<node_t> ids(m_n);
        node_t val = 0;
        std::stack<node_t> stk;
        stk.emplace(0);
        while(!stk.empty()) {
            auto f = stk.top();
            stk.pop();
            ids[f] = val; ++val;
            if(m_tree.find(f) == m_tree.end()) { continue; }
            for(const auto& t : m_tree.at(f)) { stk.emplace(t); }
        }
        return ids;
    }

    auto constructOrder()const {
        std::vector<node_t> order(m_n);
        for(ll i = 0; i < m_n; ++i) { order[m_ids[i]] = i; }
        return order;
    }
    /*
     * 辺をnodeとして拡張した場合の辺nodeだけIDを振る
     * (1) - (2)
     * (1) - (e) - (2)
     * [-1, -1, 0]
     */
    auto constructEdgeIds() const {
        node_t edge_size = (m_n >> 1);
        std::vector<node_t> edge_ids(m_n, -1);
        node_t val = 0;
        std::stack<node_t> stk;
        stk.emplace(0);
        while(!stk.empty()) {
            auto f = stk.top();
            stk.pop();
            if(f > edge_size) { edge_ids[f] = val; ++val; }
            if(m_tree.find(f) == m_tree.end()) { continue; }
            for(const auto& t : m_tree.at(f)) { stk.emplace(t); }
        }
        return edge_ids;
    }

public:

    HLD(node_t n, const Graph_f& tree) :
        m_n(n),
        m_tree(constructGraph(n, tree)),
        m_root_par(constructRootPar(n, m_tree)),
        m_height(constructHeight(n, m_tree)),
        m_ids(constructIds()),
        m_order(constructOrder()),
        m_edge_ids(constructEdgeIds()) {
        dump(m_order, m_ids);
    }

    auto getId(node_t i)const { return m_ids[i]; }
    auto getOrder(node_t i)const { return m_order[i]; }

    auto lca(node_t f, node_t t)const {
        do {
            auto [fr, fp] = m_root_par[f];
            auto [tr, tp] = m_root_par[t];
            if(fr == tr) { break; }
            auto fph = (fp > -1) ? m_height[fp] : -1;
            auto tph = (tp > -1) ? m_height[tp] : -1;
            if(fph < tph) { t = tp; } else { f = fp; }
        } while(true);
        return (m_height[f] < m_height[t]) ? f : t;
    }

    auto range(node_t f, node_t t)const {
        std::deque<std::pair<node_t, node_t>> ret;
        auto add = [&](node_t f, node_t t) {
            auto l = std::min(m_ids[f], m_ids[t]);
            auto r = std::max(m_ids[f], m_ids[t]);
            ret.emplace_back(l, r);
        };
        do {
            auto [fr, fp] = m_root_par[f];
            auto [tr, tp] = m_root_par[t];
            if(fr == tr) { add(f, t); break; }
            auto fph = (fp > -1) ? m_height[fp] : -1;
            auto tph = (tp > -1) ? m_height[tp] : -1;
            if(fph < tph) { add(t, tr); t = tp; } else { add(f, fr); f = fp; }
        } while(true);
        return ret;
    }

    auto rangeEdge(node_t f, node_t t)const {
        node_t edge_size = (m_n >> 1);
        std::deque<std::pair<node_t, node_t>> ret;
        auto add = [&](node_t f, node_t t) {
            auto l = std::min(m_ids[f], m_ids[t]);
            auto r = std::max(m_ids[f], m_ids[t]);
            if(m_order[l] <= edge_size) { ++l; }
            if(m_order[r] <= edge_size) { --r; }
            if(l > r) { return; }
            auto edge_l = m_edge_ids[m_order[l]];
            auto edge_r = m_edge_ids[m_order[r]];
            ret.emplace_back(edge_l, edge_r);
        };
        do {
            auto [fr, fp] = m_root_par[f];
            auto [tr, tp] = m_root_par[t];
            if(fr == tr) { add(f, t); break; }
            auto fph = (fp > -1) ? m_height[fp] : -1;
            auto tph = (tp > -1) ? m_height[tp] : -1;
            if(fph < tph) { add(t, tr); t = tp; } else { add(f, fr); f = fp; }
        } while(true);
        return ret;
    }
};

signed main() {

    ll n;
    cin >> n;
    unordered_multimap<ll, ll> tree;
    REP(_, n - 1) {
        ll f, t;
        cin >> f >> t;
        --f; --t;
        tree.emplace(f, t);
        tree.emplace(t, f);
    }

    auto segtree = SegmentTree(n, 0);
    auto hld = HLD(n, tree);

    ll q;
    cin >> q;
    REP(_, q) {
        ll a, b;
        cin >> a >> b;
        --a; --b;
        for(const auto& [l, r] : hld.range(a, b)) {
            segtree.add(l, r, 1);
        }
    }

    ll ans = 0;
    REP(i, n) {
        auto val = segtree.query(i, i);
        ans += val * (val + 1) / 2;
    }
    cout << ans << endl;
}
yukicoder

結果

テストケース

ソースコード
