제출 #1147965

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1147965		onbert	Construction of Highway (JOI18_construction)	C++20	100 / 100	1040 ms	33988 KiB

construction

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 1e5 + 5, maxN = 4e5 + 5, lg = 18;
int n;
bool vis[maxn];
int a[maxn];
vector<int> adj[maxn];
int newid[maxn], out[maxn], cnt = 0;
int binlift[maxn][lg];

void dfs(int u) {
    cnt++;
    newid[u] = cnt;
    for (int i=1;i<lg;i++) {
        if (!binlift[u][i-1]) break;
        binlift[u][i] = binlift[binlift[u][i-1]][i-1];
    }
    for (int v:adj[u]) {
        adj[v].erase(find(adj[v].begin(), adj[v].end(), u));
        binlift[v][0] = u;
        dfs(v);
    }
    out[u] = cnt;
}

int seg[maxN];
void update(int id, int l, int r, int target, int val) {
    if (r < target || target < l) return;
    if (l == r) {
        seg[id] = val;
        return;
    }
    int mid = (l+r)/2;
    update(id*2, l, mid, target, val); update(id*2+1, mid+1, r, target, val);
    seg[id] = max(seg[id*2], seg[id*2+1]);
}
int mx(int id, int l, int r, int findl, int findr) {
    if (r < findl || findr < l) return 0;
    if (findl <= l && r <= findr) return seg[id];
    int mid = (l+r)/2;
    return max(mx(id*2, l, mid, findl, findr), mx(id*2+1, mid+1, r, findl, findr));
}


struct thing {
    int val, freq, id;
    bool operator < (const thing &b) const {
        return val > b.val;
    }
};
int fen[maxn];
void fenupdate(int id, int val) {
    while (id <= n) {
        fen[id] += val;
        id += (id & -id);
    }
}
int sum(int id) {
    int val = 0;
    while (id >= 1) {
        val += fen[id];
        id -= (id & -id);
    }
    return val;
}

int solve(vector<pair<int,int>> VEC) {
    // for (auto [x, y]:VEC) cout << x << " " << y << endl;

    int sz = VEC.size();

    // int funny = 0;
    // for (int i=0;i<sz;i++) for (int j=i+1;j<sz;j++) {
    //     if (VEC[i].first > VEC[j].first) funny += VEC[i].second * VEC[j].second;
    // }
    // return funny;

    vector<thing> vec;
    for (int i=0;i<sz;i++) vec.push_back({VEC[i].first, VEC[i].second, i+1});
    sort(vec.begin(), vec.end());
    vector<pair<int,int>> temp;
    int ans = 0, last = 0;
    for (int i=0;i<=sz;i++) fen[i] = 0;
    for (auto [val, freq, id]:vec) {
        if (val != last) {
            for (auto [x, j]:temp) fenupdate(j, x);
            temp.clear();
            last = val;
        }
        ans += sum(id) * freq;
        temp.push_back({freq, id});
    }
    return ans;
}

signed main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n;
    for (int i=1;i<=n;i++) cin >> a[i];
    pair<int,int> qry[n+1];
    vis[1] = true;
    qry[1] = {0, 1};
    for (int i=2;i<=n;i++) {
        int u, v;
        cin >> u >> v;
        if (vis[u]) qry[i] = {u, v}, vis[v] = true;
        else qry[i] = {v, u}, vis[u] = true;
        adj[u].push_back(v); adj[v].push_back(u);
    }
    dfs(1);
    update(1, 1, n, 1, 1);
    for (int i=2;i<=n;i++) {
        auto [u, v] = qry[i];
        vector<pair<int,int>> vec;
        while (u) {
            int val = mx(1, 1, n, newid[u], out[u]);
            int freq = 1;
            for (int i=lg-1;i>=0;i--) {
                int cur = binlift[u][i];
                if (cur && mx(1, 1, n, newid[cur], out[cur]) == val) u = cur, freq += (1<<i);
            }
            vec.push_back({a[qry[val].second], freq});
            u = binlift[u][0];
            // cout << newid[u] << " " << out[u] << endl;
            // cout << v << " " << mx(1, 1, n, newid[v], out[v]) << endl;
        }
        reverse(vec.begin(), vec.end());
        cout << solve(vec) << "\n";
        update(1, 1, n, newid[v], i);
        // if (i==1) cout << v << " " << newid[v] << endl;
    }
}

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