제출 #1147950

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1147950		onbert	Construction of Highway (JOI18_construction)	C++20	0 / 100	2 ms	2632 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();
    vector<thing> vec;
    for (int i=0;i<sz;i++) vec.push_back({VEC[i].first, VEC[i].second, i});
    sort(vec.begin(), vec.end());
    vector<pair<int,int>> temp;
    int ans = 0, last = -1;
    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+1, x);
            temp.clear();
        }
        ans += sum(id+1);
        temp.push_back({freq, id+1});
    }
    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 = {{a[v], 0}};
        while (true) {
            int cmp = mx(1, 1, n, newid[v], out[v]);
            for (int i=lg-1;i>=0;i--) {
                int cur = binlift[v][i];
                if (cur && mx(1, 1, n, newid[cur], out[cur]) == cmp) v = cur, vec.back().second += (1<<i);
            }
            v = binlift[v][0];
            if (v == 0) break;
            // cout << newid[u] << " " << out[u] << endl;
            // cout << v << " " << mx(1, 1, n, newid[v], out[v]) << endl;
            vec.push_back({a[qry[mx(1, 1, n, newid[v], out[v])].second], 1});
        }
        reverse(vec.begin(), vec.end());
        vec.pop_back();
        cout << solve(vec) << endl;
        update(1, 1, n, newid[qry[i].second], i);
        // if (i==1) cout << v << " " << newid[v] << endl;
    }
}

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