lessons/参考实现/08-高级线段树与树状数组/HYSBZ-2212.cpp

#include <iostream>
#include <vector>
using namespace std;
struct Node { int left = 0, right = 0, count = 0; };
int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n; cin >> n;
    vector<int> token(2 * n - 1); for (int &x : token) cin >> x;
    vector<Node> tree(1); tree.reserve(static_cast<size_t>(n) * 20);
    auto insert = [&](auto &&self, int l, int r, int position) -> int {
        int u = tree.size(); tree.push_back({}); tree[u].count = 1;
        if (l < r) { int mid = (l + r) / 2; if (position <= mid) tree[u].left = self(self, l, mid, position); else tree[u].right = self(self, mid + 1, r, position); }
        return u;
    };
    auto merge = [&](auto &&self, int a, int b, int l, int r, long long &normal, long long &swapped) -> int {
        if (!a) return b; if (!b) return a;
        if (l < r) {
            normal += 1LL * tree[tree[a].right].count * tree[tree[b].left].count;
            swapped += 1LL * tree[tree[b].right].count * tree[tree[a].left].count;
            int mid = (l + r) / 2;
            tree[a].left = self(self, tree[a].left, tree[b].left, l, mid, normal, swapped);
            tree[a].right = self(self, tree[a].right, tree[b].right, mid + 1, r, normal, swapped);
        }
        tree[a].count += tree[b].count; return a;
    };
    vector<int> stack; long long answer = 0;
    for (int i = static_cast<int>(token.size()) - 1; i >= 0; --i) {
        if (token[i] != 0) stack.push_back(insert(insert, 1, n, token[i]));
        else {
            int left = stack.back(); stack.pop_back(); int right = stack.back(); stack.pop_back();
            long long normal = 0, swapped = 0;
            stack.push_back(merge(merge, left, right, 1, n, normal, swapped));
            answer += min(normal, swapped);
        }
    }
    cout << answer << '\n';
}