Submission #1312894

#	Time	Username	Problem	Language	Result	Execution time	Memory
1312894		orzorzorz	Construction of Highway (JOI18_construction)	C++20	100 / 100	671 ms	25540 KiB

construction

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>

using namespace std;

typedef long long ll;

const int MAXN = 100005;
int N;
ll C[MAXN];
vector<int> adj[MAXN];
int parent[MAXN], depth[MAXN], sz[MAXN], son[MAXN];
int top[MAXN], pos[MAXN], dfn_timer;

// 1. 樹狀數組 (BIT) 用於計算逆序對
ll bit[MAXN];
void update(int i, int delta) {
    for (; i <= N; i += i & -i) bit[i] += delta;
}
ll query(int i) {
    ll s = 0;
    for (; i > 0; i -= i & -i) s += bit[i];
    return s;
}

// 2. HLD 預處理
void dfs_sz(int u, int p, int d) {
    parent[u] = p; depth[u] = d; sz[u] = 1;
    for (int v : adj[u]) {
        dfs_sz(v, u, d + 1);
        sz[u] += sz[v];
        if (sz[v] > sz[son[u]]) son[u] = v;
    }
}

void dfs_hld(int u, int t) {
    top[u] = t; pos[u] = ++dfn_timer;
    if (son[u]) dfs_hld(son[u], t);
    for (int v : adj[u]) {
        if (v != son[u]) dfs_hld(v, v);
    }
}

// 3. 管理顏色段的結構
struct Node {
    int l, r, val;
    bool operator<(const Node& other) const { return l < other.l; }
};
set<Node> segments;

// 拆分段 (珂朵莉樹技巧)
auto split(int p) {
    auto it = segments.lower_bound({p, 0, 0});
    if (it != segments.end() && it->l == p) return it;
    --it;
    int l = it->l, r = it->r, v = it->val;
    segments.erase(it);
    segments.insert({l, p - 1, v});
    return segments.insert({p, r, v}).first;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0);

    cin >> N;
    vector<ll> vals;
    for (int i = 1; i <= N; i++) {
        cin >> C[i];
        vals.push_back(C[i]);
    }
    
    // 離散化
    sort(vals.begin(), vals.end());
    vals.erase(unique(vals.begin(), vals.end()), vals.end());
    auto get_val = [&](ll x) {
        return lower_bound(vals.begin(), vals.end(), x) - vals.begin() + 1;
    };

    vector<pair<int, int>> queries;
    for (int i = 0; i < N - 1; i++) {
        int u, v; cin >> u >> v;
        adj[u].push_back(v);
        queries.push_back({u, v});
    }

    dfs_sz(1, 0, 1);
    dfs_hld(1, 1);

    // 初始化：每個城市一開始都是自己的初始值
    for (int i = 1; i <= N; i++) {
        segments.insert({pos[i], pos[i], get_val(C[i])});
    }

    for (auto& q : queries) {
        int u = q.first, b_val = get_val(C[q.second]);
        vector<pair<int, int>> path_segments; // {value, length}
        
        int curr = u;
        while (curr) {
            int l = pos[top[curr]], r = pos[curr];
            auto it_r = split(r + 1);
            auto it_l = split(l);
            
            vector<Node> temp;
            for (auto it = it_l; it != it_r; ++it) temp.push_back(*it);
            
            // HLD 跳轉是從下往上，所以存入時要反轉順序
            reverse(temp.begin(), temp.end());
            for (auto& node : temp) {
                path_segments.push_back({node.val, node.r - node.l + 1});
            }
            
            segments.erase(it_l, it_r);
            segments.insert({l, r, b_val});
            curr = parent[top[curr]];
        }

        // 計算逆序對：從根節點往葉子節點看
        reverse(path_segments.begin(), path_segments.end());
        ll cost = 0;
        ll total_count = 0;
        for (auto& seg : path_segments) {
            // 逆序對定義：s 在 t 前面且 val[s] > val[t]
            // 我們統計 BIT 中比當前值大的個數
            cost += (ll)seg.second * (total_count - query(seg.first));
            update(seg.first, seg.second);
            total_count += seg.second;
        }

        // 清理 BIT 以供下次使用
        for (auto& seg : path_segments) update(seg.first, -seg.second);
        
        cout << cost << "\n";
    }

    return 0;
}

Compilation message (stderr)

construction.cpp: In function 'int main()':
construction.cpp:93:49: warning: narrowing conversion of 'get_val.main()::<lambda(ll)>(C[i])' from 'long int' to 'int' [-Wnarrowing]
   93 |         segments.insert({pos[i], pos[i], get_val(C[i])});
      |                                          ~~~~~~~^~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 9 / 9
• Subtask 3: 84 / 84