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

提出ソース
結果

問題	No.399 動的な領主
コンテスト
ユーザー	TakumiShimoda
提出日時	2022-04-12 02:57:50
言語	C++17 (gcc 13.3.0 + boost 1.87.0)
結果	AC
実行時間	564 ms / 2,000 ms
コード長	14,407 bytes
コンパイル時間	5,524 ms
コンパイル使用メモリ	267,000 KB
最終ジャッジ日時	2025-01-28 17:30:07
ジャッジサーバーID （参考情報）	judge2 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン	結果
other	AC * 19
権限があれば一括ダウンロードができます
ソースコード

raw source code
#include <bits/stdc++.h>
using namespace std;
#include <atcoder/all>
using namespace atcoder;

#define int long long

typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ld;
typedef pair<int, int> pi;
typedef vector<int> vi;
typedef vector<double> vd;
typedef vector<bool> vb;
typedef vector<string> vs;
typedef vector<char> vc;
typedef vector<pair<int, int>> vp;
typedef vector<vector<int>> vvi;
typedef vector<vector<double>> vvd;
typedef vector<vector<bool>> vvb;
typedef vector<vector<string>> vvs;
typedef vector<vector<char>> vvc;
typedef vector<vector<pair<int, int>>> vvp;
typedef vector<vector<vector<int>>> vvvi;
typedef vector<vector<vector<vector<int>>>> vvvvi;
typedef queue<int> qi;
typedef queue<pair<int, int>> qp;
template <typename T>
using vvv = vector<vector<vector<T>>>;
template <typename T>
using vvvv = vector<vector<vector<vector<T>>>>;
template <typename T>
using pq = priority_queue<T>;
template <typename T>
using pqg = priority_queue<T, vector<T>, greater<T>>;

#define _PI 3.14159265358979323846
#define _E 2.7182818284590452354
#define fi first
#define se second
#define mset multiset
#define uset unordered_set
#define umap unordered_map
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define mt make_tuple
#define td typedef
#define elif else if
#define unless(a) if (!(a))
#define el endl
#define all(obj) (obj).begin(), (obj).end()
#define rall(obj) (obj).rbegin(), (obj).rend()
#define acc(a) accumulate(all(a), 0LL)
#define lb(v, a) (lower_bound(begin(v), end(v), a) - begin(v))
#define ub(v, a) (upper_bound(begin(v), end(v), a) - begin(v))
#define cbit(x) __builtin_popcountll(x)
#define bits(x) (1LL << (x))
#define gbit(a, i) ((a >> i) & 1)
#define topbit(t) (t == 0 ? -1 : 63 - __builtin_clzll(t))
#define botbit(t) (t == 0 ? 64 : __builtin_ctzll(t))

#define rep1(a) for (int i = 0; i < (int)a; i++)
#define rep2(i, a) for (int i = 0; i < (int)a; i++)
#define rep3(i, a, b) for (int i = a; i < (int)b; i++)
#define rep4(i, a, b, c) for (int i = a; i < (int)b; i += c)
#define overload4(a, b, c, d, e, ...) e
#define rep(...) overload4(__VA_ARGS__, rep4, rep3, rep2, rep1)(__VA_ARGS__)
#define rrep1(n) for (ll i = n; i--;)
#define rrep2(i, n) for (ll i = n; i--;)
#define rrep3(i, a, b) for (ll i = b; i-- > (a);)
#define rrep4(i, a, b, c) \
    for (ll i = (a) + ((b) - (a)-1) / (c) * (c); i >= (a); i -= c)
#define rrep(...) \
    overload4(__VA_ARGS__, rrep4, rrep3, rrep2, rrep1)(__VA_ARGS__)
#define fore1(i, a) for (auto &&i : a)
#define fore2(x, y, a) for (auto &&[x, y] : a)
#define fore3(x, y, z, a) for (auto &&[x, y, z] : a)
#define fore(...) overload4(__VA_ARGS__, fore3, fore2, fore1)(__VA_ARGS__)

// debug methods
// usage: debug(x,y);
#define CHOOSE(a) CHOOSE2 a
#define CHOOSE2(a0, a1, a2, a3, a4, x, ...) x
#define debug_1(x1) cout << #x1 << ": " << x1 << endl
#define debug_2(x1, x2) \
    cout << #x1 << ": " << x1 << ", " #x2 << ": " << x2 << endl
#define debug_3(x1, x2, x3)                                                 \
    cout << #x1 << ": " << x1 << ", " #x2 << ": " << x2 << ", " #x3 << ": " \
         << x3 << endl
#define debug_4(x1, x2, x3, x4)                                             \
    cout << #x1 << ": " << x1 << ", " #x2 << ": " << x2 << ", " #x3 << ": " \
         << x3 << ", " #x4 << ": " << x4 << endl
#define debug_5(x1, x2, x3, x4, x5)                                         \
    cout << #x1 << ": " << x1 << ", " #x2 << ": " << x2 << ", " #x3 << ": " \
         << x3 << ", " #x4 << ": " << x4 << ", " #x5 << ": " << x5 << endl
#ifdef _DEBUG
#define debug(...)                                                        \
    CHOOSE((__VA_ARGS__, debug_5, debug_4, debug_3, debug_2, debug_1, ~)) \
    (__VA_ARGS__)
#else
#define debug(...)
#endif

istream &operator>>(istream &is, modint998244353 &a) {
    long long v;
    is >> v;
    a = v;
    return is;
}
ostream &operator<<(ostream &os, const modint998244353 &a) {
    return os << a.val();
}
istream &operator>>(istream &is, modint1000000007 &a) {
    long long v;
    is >> v;
    a = v;
    return is;
}
ostream &operator<<(ostream &os, const modint1000000007 &a) {
    return os << a.val();
}
template <int m>
istream &operator>>(istream &is, static_modint<m> &a) {
    long long v;
    is >> v;
    a = v;
    return is;
}
template <int m>
istream &operator>>(istream &is, dynamic_modint<m> &a) {
    long long v;
    is >> v;
    a = v;
    return is;
}
template <int m>
ostream &operator<<(ostream &os, const static_modint<m> &a) {
    return os << a.val();
}
template <int m>
ostream &operator<<(ostream &os, const dynamic_modint<m> &a) {
    return os << a.val();
}
template <class T>
istream &operator>>(istream &is, vector<T> &v) {
    for (auto &e : v) is >> e;
    return is;
}
template <class T>
ostream &operator<<(ostream &os, const vector<T> &v) {
    for (auto &e : v) os << e << ' ';
    return os;
}
template <class T>
ostream &operator<<(ostream &os, const vector<vector<T>> &v) {
    for (auto &e : v) {
        for (auto &c : e) os << c << ' ';
        os << endl;
    }
    return os;
}
template <class T, class U>
istream &operator>>(istream &is, pair<T, U> &p) {
    is >> p.first >> p.second;
    return is;
}
template <class T, class U>
ostream &operator<<(ostream &os, const pair<T, U> &p) {
    os << p.first << "," << p.second;
    return os;
}
template <class T>
ostream &operator<<(ostream &s, set<T> P) {
    fore(it, P) {
        s << it << " ";
    }
    return s;
}
template <class T1, class T2>
ostream &operator<<(ostream &s, map<T1, T2> P) {
    fore(x, y, P) {
        s << "<" << x << "->" << y << "> ";
    }
    return s;
}
template <class T>
ostream &operator<<(ostream &s, multiset<T> P) {
    fore(it, P) {
        s << it << " ";
    }
    return s;
}
template <class T>
ostream &operator<<(ostream &s, unordered_set<T> P) {
    fore(it, P) {
        s << it << " ";
    }
    return s;
}
template <class T1, class T2>
ostream &operator<<(ostream &s, unordered_map<T1, T2> P) {
    fore(x, y, P) {
        s << "<" << x << "->" << y << "> ";
    }
    return s;
}
struct fast_ios {
    fast_ios() {
        cin.tie(nullptr);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(12);
    };
} fast_ios_;

vector<int> iota(int n, int s = 0) {
    vi a(n);
    iota(a.begin(), a.end(), s);
    return a;
}
template <class T>
void sort(vector<T> &v) {
    sort(all(v));
}
template <class T>
void rsort(vector<T> &v) {
    sort(rall(v));
}
template <class T>
void reverse(vector<T> &v) {
    reverse(all(v));
}
template <class T>
auto min(const T &a) {
    return *min_element(all(a));
}
template <class T>
auto max(const T &a) {
    return *max_element(all(a));
}
template <class T>
bool chmax(T &a, const T &b) {
    if (a < b) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
bool chmin(T &a, const T &b) {
    if (b < a) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
vector<T> uniq(vector<T> v) {
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
    return v;
}
template <class T>
vector<T> compress(vector<T> v) {
    vector<T> v2(v.size());
    v2 = v;
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());

    for (int i = 0; i < v2.size(); i++) {
        v2[i] = lower_bound(v.begin(), v.end(), v2[i]) - v.begin();
    }
    return v2;
}
template <typename T>
vector<T> sumv(vector<T> &v) {
    vector<T> res(v.size());
    for (int i = 0; i < v.size(); i++) {
        res[i] = i > 0 ? res[i - 1] + v[i] : v[0];
    }
    return res;
}
template <typename T>
vector<vector<T>> sumv(vector<vector<T>> &v) {
    int h = v.size(), w = v[0].size();
    cout << h << " " << w << el;
    vector<vector<T>> res(h, vector<T>(w));
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            res[i][j] = v[i][j];
            if (i) res[i][j] += res[i - 1][j];
            if (j) res[i][j] += res[i][j - 1];
            if (i > 0 && j > 0) res[i][j] -= res[i - 1][j - 1];
        }
    }
    return res;
}
template <class T>
T exp(T x, ll n) {
    T res = 1;
    while (n > 0) {
        if (n & 1) res = res * x;
        x = x * x;
        n >>= 1;
    }
    return res;
}
constexpr ll ten(int n) {
    return n == 0 ? 1 : ten(n - 1) * 10;
}
long long ceil(long long x, long long y) {
    return (x + y - 1) / y;
}
void yesno(bool x) {
    if (x) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
}

int dx[8] = {1, 0, -1, 0, 1, 1, -1, -1};
int dy[8] = {0, 1, 0, -1, -1, 1, 1, -1};

long long inf = 2000000000005000005;

// using mint = static_modint<1000000009>;
// using mint = dynamic_modint<1000000009>;
// long long mod = 1000000007;
// using mint = modint1000000007;
// long long mod = 998244353;
// using mint = modint998244353;
// typedef vector<mint> vm;
// typedef vector<vector<mint>> vvm;
// typedef vector<vector<vector<mint>>> vvvm;
////////////////////////////////////////////////////////////////////////////////////////////
/*
https://algo-logic.info/binary-indexed-tree/#toc_id_5_5 を参考に

BIT: RAQ対応BIT
初期値は a_1 = a_2 = ... = a_n = 0
・add(l,r,x): [l,r) に x を加算する
・sum(i): a_1 + a_2 + ... + a_i を計算する
計算量は全て O(logn)
*/
template <typename T>
struct BIT {
    int n;             // 要素数
    vector<T> bit[2];  // データの格納先
    BIT(int n_) {
        init(n_);
    }
    void init(int n_) {
        n = n_ + 1;
        for (int p = 0; p < 2; p++) bit[p].assign(n, 0);
    }

    void add_sub(int p, int i, T x) {
        for (int idx = i; idx < n; idx += (idx & -idx)) {
            bit[p][idx] += x;
        }
    }
    void add(int l, int r, T x) {  // [l,r) に加算
        add_sub(0, l, -x * (l - 1));
        add_sub(0, r, x * (r - 1));
        add_sub(1, l, x);
        add_sub(1, r, -x);
    }

    T sum_sub(int p, int i) {
        T s(0);
        for (int idx = i; idx > 0; idx -= (idx & -idx)) {
            s += bit[p][idx];
        }
        return s;
    }
    T sum(int i) {
        return sum_sub(0, i) + sum_sub(1, i) * i;
    }
};
/*
https://github.com/drken1215/algorithm/blob/master/DataStructureOnTree/heavy_light_decomposition.cpp
を参考に

HLDecomposition hld(G):インスタンス生成
hld.build():HL木生成
foreach_nodes(u,v,function f):[u,v]間の頂点に対するクエリ
foreach_edge(u,v,fucntion f):[u,v]間の辺に対するクエリ

vid: id of v after HL-Decomposition
inv: inv[vid[v]] = v
par: id of parent
depth
subsize: size of subtree
head: head-id in the heavy-path
prev, next: prev-id, next-id in the heavy-path
type: the id of tree for forest
vend: the last-id of node in v-subtree
*/
typedef vector<vector<int>> Graph;
struct HLDecomposition {
    int n;
    Graph G;
    vector<int> vid, inv, par, depth, subsize, head, prev, next, type;

    // construct
    HLDecomposition() {
    }
    HLDecomposition(const Graph &G_)
        : n((int)G_.size()),
          G(G_),
          vid(n, -1),
          inv(n),
          par(n),
          depth(n),
          subsize(n, 1),
          head(n),
          prev(n, -1),
          next(n, -1),
          type(n) {
    }
    void build(vector<int> roots = {0}) {
        int curtype = 0, pos = 0;
        for (auto r : roots)
            decide_heavy_edge(r), reconstruct(r, curtype++, pos);
    }
    void decide_heavy_edge(int r) {
        stack<pair<int, int>> st;
        par[r] = -1, depth[r] = 0;
        st.emplace(r, 0);
        while (!st.empty()) {
            int v = st.top().first;
            int &i = st.top().second;
            if (i < (int)G[v].size()) {
                int e = G[v][i++];
                if (e == par[v]) continue;
                par[e] = v, depth[e] = depth[v] + 1;
                st.emplace(e, 0);
            } else {
                st.pop();
                int maxsize = 0;
                for (auto e : G[v]) {
                    if (e == par[v]) continue;
                    subsize[v] += subsize[e];
                    if (maxsize < subsize[e])
                        maxsize = subsize[e], prev[e] = v, next[v] = e;
                }
            }
        }
    }
    void reconstruct(int r, int curtype, int &pos) {
        stack<int> st({r});
        while (!st.empty()) {
            int start = st.top();
            st.pop();
            for (int v = start; v != -1; v = next[v]) {
                type[v] = curtype;
                vid[v] = pos++;
                inv[vid[v]] = v;
                head[v] = start;
                for (auto e : G[v])
                    if (e != par[v] && e != next[v]) st.push(e);
            }
        }
    }

    // node query [u, v], f([left, right])
    void foreach_nodes(int u, int v, const function<void(int, int)> &f) {
        while (true) {
            if (vid[u] > vid[v]) swap(u, v);
            f(max(vid[head[v]], vid[u]), vid[v]);
            if (head[u] != head[v])
                v = par[head[v]];
            else
                break;
        }
    }

    // edge query [u, v], f([left, right])
    void foreach_edges(int u, int v, const function<void(int, int)> &f) {
        while (true) {
            if (vid[u] > vid[v]) swap(u, v);
            if (head[u] != head[v]) {
                f(vid[head[v]], vid[v]);
                v = par[head[v]];
            } else {
                if (u != v) {
                    f(vid[u] + 1, vid[v]);
                }
                break;
            }
        }
    }

    // LCA
    int lca(int u, int v) {
        while (true) {
            if (vid[u] > vid[v]) swap(u, v);
            if (head[u] == head[v]) return u;
            v = par[head[v]];
        }
    }
};

////////////////////////////////////////////////////////////////////////////////////////////

signed main() {
    int n;
    cin >> n;
    vvi g(n);
    rep(i, n - 1) {
        int u, v;
        cin >> u >> v;
        u--;
        v--;
        g[u].pb(v);
        g[v].pb(u);
    }
    HLDecomposition hl(g);
    hl.build();
    BIT<int> bit(n + 5);
    int ans = 0;
    int q;
    cin >> q;
    rep(q) {
        int a, b;
        cin >> a >> b;
        a--;
        b--;
        hl.foreach_nodes(a, b, [&](int l, int r) {
            bit.add(l + 1, r + 2, 1);
            ans += bit.sum(r + 1) - bit.sum(l);
        });
    }
    cout << ans << el;
}
yukicoder

結果

ソースコード
