代码

#pragma GCC target("avx2")

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

static unsigned* answers;

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 Workspace {
    vector<Row<D>> aux[2];
    Workspace<D - 1> lower;

    explicit Workspace(size_t n) : lower(n) {
        aux[0].resize(n);
        aux[1].resize(n);
    }
};

template <>
struct Workspace<1> {
    vector<Row<1>> aux[2];

    explicit Workspace(size_t n) {
        aux[0].resize(n);
        aux[1].resize(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>
static inline Row<D - 1> drop_first_impl(
    const Row<D>& row, unsigned query, index_sequence<I...>) {
    return Row<D - 1>{get<I + 1>(row)..., query};
}

template <size_t D>
static inline Row<D - 1> drop_first(
    const Row<D>& row, unsigned query) {
    return drop_first_impl<D>(
        row, query, make_index_sequence<D - 1>{});
}

template <size_t D, size_t... I>
static inline Row<D> make_input_row_impl(
    const unsigned* const* x, unsigned i, index_sequence<I...>) {
    return Row<D>{x[I][i]..., i + 1};
}

template <size_t D>
static inline Row<D> make_input_row(
    const unsigned* const* x, unsigned i) {
    return make_input_row_impl<D>(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 Row<D>& a, const Row<D>& 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>> lower;
    lower.reserve(r - l);
    for (unsigned i = l; i < r; ++i)
        lower.emplace_back(drop_first<D>(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;
        }
        answers[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;
                answers[get<D>(items[i])] += count;
            }
        }
        sort(
            items.begin() + l, items.begin() + r,
            [](const Row<D>& a, const Row<D>& 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.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.aux[!id], lm, m, mr);
    else
        count_static<D>(
            workspace.aux[!id], items, workspace.lower, lm, m, mr);

    if constexpr (Root)
        return UINT_MAX;

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

template <size_t D>
static void count_dynamic(
    vector<Row<D>>& items, Workspace<D>& workspace) {
    count_dynamic_recursion<D, true>(
        items, workspace, 0, 0, items.size());
}

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])) {
            events.emplace_back(drop_first<D>(queries[point], 0));
            ++point;
        } else {
            events.emplace_back(
                drop_first<D>(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) {
    answers = out - 1;
    memset(out, 0, sizeof(unsigned) * n);

    vector<Row<D>> queries;
    queries.reserve(n + 1);
    for (unsigned i = 0; i < static_cast<unsigned>(n); ++i)
        queries.emplace_back(make_input_row<D>(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);
}

评测结果