代码

#pragma GCC target("avx2")

#include <algorithm>
#include <climits>
#include <cstdint>
#include <cstring>
#include <tuple>
#include <utility>
#include <vector>
using namespace std;

static uintptr_t answer_base;

template <size_t... I>
static auto row_type(index_sequence<I...>)
    -> tuple<decltype((void)I, unsigned{})...>;

template <size_t D>
using Row = decltype(row_type(make_index_sequence<D + 1>{}));

template <size_t D>
struct Buffers {
    vector<Row<D>> aux[2];

    __attribute__((always_inline)) explicit Buffers(size_t n) {
        aux[0].resize(n);
        aux[1].resize(n);
    }
};

template <size_t D>
struct Workspace {
    Buffers<D> current;
    Workspace<D - 1> lower;
    vector<Row<D>> scratch;

    __attribute__((always_inline))
    explicit Workspace(size_t n) : current(n), lower(n) {}
};

template <>
struct Workspace<1> {
    Buffers<1> current;
    vector<Row<1>> scratch;

    __attribute__((always_inline)) explicit Workspace(size_t n) : current(n) {}
};

template <size_t D, size_t... I>
static inline bool coordinates_less_impl(
    const Row<D>& a, const Row<D>& b, index_sequence<I...>) {
    return ((get<I>(a) < get<I>(b)) && ...);
}

template <size_t D>
static inline bool coordinates_less(const Row<D>& a, const Row<D>& b) {
    return coordinates_less_impl<D>(a, b, make_index_sequence<D>{});
}

template <size_t D, size_t... I>
__attribute__((always_inline, flatten)) static inline void
emplace_drop_first_impl(
    vector<Row<D - 1>>& rows,
    const Row<D>& row,
    unsigned query,
    index_sequence<I...>) {
    rows.emplace_back(get<I + 1>(row)..., query);
}

template <size_t D>
static inline void emplace_drop_first(
    vector<Row<D - 1>>& rows, const Row<D>& row, unsigned query) {
    emplace_drop_first_impl<D>(
        rows, row, query, make_index_sequence<D - 1>{});
}

template <size_t D, size_t... I>
static inline void emplace_input_row_impl(
    vector<Row<D>>& rows,
    const unsigned* const* x,
    unsigned i,
    index_sequence<I...>) {
    rows.emplace_back(x[I][i]..., i + 1);
}

template <size_t D>
static inline void emplace_input_row(
    vector<Row<D>>& rows, const unsigned* const* x, unsigned i) {
    emplace_input_row_impl<D>(
        rows, x, i, make_index_sequence<D>{});
}

template <size_t D, size_t... I>
static inline Row<D> make_sentinel_impl(index_sequence<I...>) {
    return Row<D>{((void)I, UINT_MAX)..., 0};
}

template <size_t D>
static inline Row<D> make_sentinel() {
    return make_sentinel_impl<D>(make_index_sequence<D>{});
}

template <size_t D>
static void count_dynamic(vector<Row<D>>& items, Workspace<D>& workspace);

template <size_t D>
static inline void count_static(
    vector<Row<D>>& items,
    vector<Row<D>>& merged,
    Workspace<D - 1>& lower_workspace,
    unsigned l,
    unsigned m,
    unsigned r) {
    merge(
        items.begin() + l, items.begin() + m,
        items.begin() + m, items.begin() + r,
        merged.begin() + l,
        [](const auto& a, const auto& b) {
            if (get<0>(a) != get<0>(b))
                return get<0>(a) < get<0>(b);
            return !!get<D>(a) > !!get<D>(b);
        });

    vector<Row<D - 1>> local;
    vector<Row<D - 1>>& lower = [&]() -> vector<Row<D - 1>>& {
        if constexpr (D == 2) {
            lower_workspace.scratch.clear();
            return lower_workspace.scratch;
        } else {
            return local;
        }
    }();
    lower.reserve(r - l);
    for (unsigned i = l; i < r; ++i)
        emplace_drop_first<D>(lower, merged[i], get<D>(merged[i]));
    count_dynamic<D - 1>(lower, lower_workspace);
}

static inline void count_static(
    vector<Row<1>>& items, unsigned l, unsigned m, unsigned r) {
    unsigned i = l;
    unsigned count = 0;
    for (unsigned j = m; j < r; ++j) {
        while (i < m && get<0>(items[i]) < get<0>(items[j])) {
            ++i;
            ++count;
        }
        *reinterpret_cast<unsigned*>(
            answer_base + sizeof(unsigned) * get<1>(items[j])) += count;
    }
}

template <size_t D, bool Root = false>
static unsigned count_dynamic_recursion(
    vector<Row<D>>& items,
    Workspace<D>& workspace,
    int id,
    unsigned l,
    unsigned r) {
    if (r - l <= 8 * (D + 1)) {
        for (unsigned i = l; i < r; ++i) {
            if (get<D>(items[i])) {
                unsigned count = 0;
                for (unsigned j = l; j < i; ++j)
                    if (!get<D>(items[j]) &&
                        coordinates_less<D>(items[j], items[i]))
                        ++count;
                *reinterpret_cast<unsigned*>(
                    answer_base + sizeof(unsigned) * get<D>(items[i])) +=
                    count;
            }
        }
        sort(
            items.begin() + l, items.begin() + r,
            [](const auto& a, const auto& b) {
                if (!!get<D>(a) != !!get<D>(b))
                    return !!get<D>(a) > !!get<D>(b);
                return a < b;
            });
        copy(
            items.begin() + l, items.begin() + r,
            workspace.current.aux[id].begin() + l);
        unsigned first_point = l;
        while (first_point < r && get<D>(items[first_point]))
            ++first_point;
        return first_point;
    }

    const unsigned m = (l + r) / 2;
    const unsigned lm =
        count_dynamic_recursion<D>(items, workspace, !id, l, m);
    const unsigned mr =
        count_dynamic_recursion<D>(items, workspace, !id, m, r);

    if constexpr (D == 1)
        count_static(workspace.current.aux[!id], lm, m, mr);
    else
        count_static<D>(
            workspace.current.aux[!id],
            items,
            workspace.lower,
            lm,
            m,
            mr);

    if constexpr (Root)
        return UINT_MAX;

    const unsigned first_point = mr - m + lm;
    merge(
        workspace.current.aux[!id].begin() + l,
        workspace.current.aux[!id].begin() + lm,
        workspace.current.aux[!id].begin() + m,
        workspace.current.aux[!id].begin() + mr,
        workspace.current.aux[id].begin() + l);
    merge(
        workspace.current.aux[!id].begin() + lm,
        workspace.current.aux[!id].begin() + m,
        workspace.current.aux[!id].begin() + mr,
        workspace.current.aux[!id].begin() + r,
        workspace.current.aux[id].begin() + first_point);
    return first_point;
}

template <size_t D>
static void count_dynamic(
    vector<Row<D>>& items, Workspace<D>& workspace) {
    const unsigned r = items.size();
    if (r <= 8 * (D + 1)) {
        count_dynamic_recursion<D>(
            items, workspace, 0, 0, r);
        return;
    }

    const unsigned m = r / 2;
    const unsigned lm =
        count_dynamic_recursion<D>(items, workspace, 1, 0, m);
    const unsigned mr =
        count_dynamic_recursion<D>(items, workspace, 1, m, r);
    if constexpr (D == 1)
        count_static(workspace.current.aux[1], lm, m, mr);
    else
        count_static<D>(
            workspace.current.aux[1],
            items,
            workspace.lower,
            lm,
            m,
            mr);
}

template <size_t D>
static void count_same_first_coordinate(vector<Row<D>>& queries) {
    vector<Row<D - 1>> events;
    int remaining = static_cast<int>(queries.size() * 2);
    events.reserve(remaining);
    queries.emplace_back(make_sentinel<D>());

    unsigned point = 0;
    unsigned query = 0;
    while (remaining--) {
        if (get<0>(queries[point]) < get<0>(queries[query])) {
            emplace_drop_first<D>(events, queries[point], 0);
            ++point;
        } else {
            emplace_drop_first<D>(
                events, queries[query], get<D>(queries[query]));
            ++query;
        }
    }
    queries.pop_back();

    Workspace<D - 1> workspace(events.size());
    count_dynamic<D - 1>(events, workspace);
}

template <size_t D>
static void count_points(
    int n, const unsigned* const* x, unsigned* out) {
    answer_base = reinterpret_cast<uintptr_t>(out) - sizeof(unsigned);
    memset(out, 0, sizeof(unsigned) * n);

    vector<Row<D>> queries;
    queries.reserve(n + 1);
    for (unsigned i = 0; i < static_cast<unsigned>(n); ++i)
        emplace_input_row<D>(queries, x, i);
    sort(queries.begin(), queries.end());
    count_same_first_coordinate<D>(queries);
}

void count_2d(
    int n, const unsigned* x, const unsigned* y, unsigned* out) {
    const unsigned* coordinates[2] = {x, y};
    count_points<2>(n, coordinates, out);
}

void count_3d(
    int n,
    const unsigned* x,
    const unsigned* y,
    const unsigned* z,
    unsigned* out) {
    const unsigned* coordinates[3] = {x, y, z};
    count_points<3>(n, coordinates, out);
}

void count_4d(int n, const unsigned* x[4], unsigned* out) {
    count_points<4>(n, x, out);
}

void count_5d(int n, const unsigned* x[5], unsigned* out) {
    count_points<5>(n, x, out);
}

评测结果