代码

#pragma GCC target("avx2,bmi,bmi2")

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

static uintptr_t answer_base;
static unsigned* answer_data;
static unsigned coordinate_bound;

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];

    Buffers() = default;

    __attribute__((always_inline)) explicit Buffers(size_t n) {
        reserve(n);
    }

    __attribute__((always_inline)) void reserve(size_t n) {
        aux[0].reserve(n);
        aux[1].reserve(n);
    }

    __attribute__((always_inline)) void resize(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) {
        scratch.reserve(n);
    }
};

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

    explicit Workspace(size_t n) {
        if (n <= 2000000) {
            current.reserve(n);
            scratch.reserve(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>
__attribute__((always_inline, flatten)) static inline void
emplace_input_event_impl(
    vector<Row<D - 1>>& rows,
    const unsigned* const* x,
    unsigned i,
    unsigned query,
    index_sequence<I...>) {
    rows.emplace_back(x[I + 1][i]..., query);
}

template <size_t D>
static inline void emplace_input_event(
    vector<Row<D - 1>>& rows,
    const unsigned* const* x,
    unsigned i,
    unsigned query) {
    emplace_input_event_impl<D>(
        rows, x, i, 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, bool fresh = false);

template <bool Fresh>
__attribute__((optimize("O3")))
static void count_1d_fenwick(const vector<Row<1>>& items) {
    vector<unsigned> tree(
        static_cast<size_t>(coordinate_bound) + 1);
    for (const Row<1>& item : items) {
        const unsigned coordinate = get<0>(item);
        const unsigned query = get<1>(item);
        if (query) {
            unsigned count = 0;
            for (unsigned i = coordinate; i; i -= i & -i)
                count += tree[i];
            if constexpr (Fresh)
                answer_data[query - 1] = count;
            else
                answer_data[query - 1] += count;
        } else {
            for (unsigned i = coordinate + 1;
                 i <= coordinate_bound;
                 i += i & -i)
                ++tree[i];
        }
    }
}

template <size_t D>
static inline void count_static(
    vector<Row<D>>& items,
    Workspace<D - 1>& lower_workspace,
    unsigned l,
    unsigned m,
    unsigned r) {
    vector<Row<D - 1>>& lower = lower_workspace.scratch;
    lower.clear();
    lower.reserve(r - l);
    unsigned i = l;
    unsigned j = m;
    while (i < m && j < r) {
        if (get<0>(items[j]) < get<0>(items[i]) ||
            (get<0>(items[j]) == get<0>(items[i]) &&
             !!get<D>(items[j]) > !!get<D>(items[i]))) {
            emplace_drop_first<D>(
                lower, items[j], get<D>(items[j]));
            ++j;
        } else {
            emplace_drop_first<D>(lower, items[i], 0);
            ++i;
        }
    }
    while (i < m) {
        emplace_drop_first<D>(lower, items[i], 0);
        ++i;
    }
    while (j < r) {
        emplace_drop_first<D>(
            lower, items[j], get<D>(items[j]));
        ++j;
    }
    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, size_t... I>
__attribute__((always_inline)) static inline bool
tail_coordinates_less_impl(
    const Row<D>& point,
    const Row<D>& query,
    index_sequence<I...>) {
    return ((get<I + 1>(point) < get<I + 1>(query)) & ...);
}

template <size_t D>
__attribute__((always_inline)) static inline bool
tail_coordinates_less(const Row<D>& point, const Row<D>& query) {
    return tail_coordinates_less_impl<D>(
        point, query, make_index_sequence<D - 1>{});
}

static uint64_t dynamic_cross_pair_limit;
static uint64_t single_role_cross_pair_limit;

template <size_t D>
__attribute__((always_inline)) static inline void count_cross(
    vector<Row<D>>& rows,
    Workspace<D>& workspace,
    unsigned first_point,
    unsigned first_query,
    unsigned end_query) {
    if (first_point == first_query || first_query == end_query)
        return;
    if constexpr (D == 1) {
        count_static(rows, first_point, first_query, end_query);
    } else {
        const unsigned point_count = first_query - first_point;
        const unsigned query_count = end_query - first_query;
        const uint64_t pairs =
            static_cast<uint64_t>(point_count) * query_count;
        if (pairs <= dynamic_cross_pair_limit) {
            unsigned eligible_end = first_point;
            for (unsigned query = first_query;
                 query < end_query;
                 ++query) {
                while (eligible_end < first_query &&
                       get<0>(rows[eligible_end]) <
                           get<0>(rows[query]))
                    ++eligible_end;
                unsigned count = 0;
                for (unsigned point = first_point;
                     point < eligible_end;
                     ++point)
                    count += tail_coordinates_less<D>(
                        rows[point], rows[query]);
                *reinterpret_cast<unsigned*>(
                    answer_base +
                    sizeof(unsigned) * get<D>(rows[query])) += count;
            }
        } else {
            count_static<D>(
                rows,
                workspace.lower,
                first_point,
                first_query,
                end_query);
        }
    }
}

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 <= 10 * (D + 1)) {
        unsigned points[10 * (D + 1)];
        unsigned point_count = 0;
        vector<Row<D>>& output = workspace.current.aux[id];
        unsigned query_write = l;
        unsigned point_write = r;
        for (unsigned i = l; i < r; ++i) {
            if (get<D>(items[i])) {
                unsigned count = 0;
                for (unsigned j = 0; j < point_count; ++j)
                    if (coordinates_less<D>(
                            items[points[j]], items[i]))
                        ++count;
                *reinterpret_cast<unsigned*>(
                    answer_base + sizeof(unsigned) * get<D>(items[i])) +=
                    count;
                output[query_write++] = items[i];
            } else {
                points[point_count++] = i;
                output[--point_write] = items[i];
            }
        }
        sort(output.begin() + l, output.begin() + query_write);
        sort(output.begin() + query_write, output.begin() + r);
        return query_write;
    }

    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);

    count_cross<D>(
        workspace.current.aux[!id], workspace, 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>
__attribute__((always_inline)) static inline void count_dynamic(
    vector<Row<D>>& items, Workspace<D>& workspace, bool fresh) {
    const unsigned r = items.size();
    if constexpr (D == 1) {
        if (r > 2000000) {
            if (fresh)
                count_1d_fenwick<true>(items);
            else
                count_1d_fenwick<false>(items);
            return;
        }
    }
    if (fresh)
        memset(
            answer_data,
            0,
            sizeof(unsigned) * coordinate_bound);
    if (workspace.current.aux[0].size() < r)
        workspace.current.resize(r);
    if (r <= 10 * (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);
    count_cross<D>(
        workspace.current.aux[1], workspace, lm, m, mr);
}

template <size_t D>
__attribute__((noinline, hot, section(".text.large"), optimize("O3")))
static void radix_sort_first(
    vector<Row<D>>& rows, unsigned bound) {
    if (rows.empty())
        return;

    constexpr unsigned radix_bits = 13;
    constexpr unsigned radix_size = 1u << radix_bits;
    constexpr unsigned radix_mask = radix_size - 1;
    unsigned offsets[radix_size];

    allocator<Row<D>> row_allocator;
    using allocator_traits_type =
        allocator_traits<allocator<Row<D>>>;
    Row<D>* const buffer =
        allocator_traits_type::allocate(row_allocator, rows.size());
    bool source_is_rows = true;
    bool buffer_constructed = false;
    unsigned maximum = bound - 1;
    for (unsigned shift = 0;; shift += radix_bits) {
        memset(offsets, 0, sizeof(offsets));
        if (source_is_rows) {
            for (const Row<D>& row : rows)
                ++offsets[(get<0>(row) >> shift) & radix_mask];
        } else {
            for (size_t i = 0; i < rows.size(); ++i)
                ++offsets[
                    (get<0>(buffer[i]) >> shift) & radix_mask];
        }

        unsigned prefix = 0;
        for (unsigned& offset : offsets) {
            const unsigned count = offset;
            offset = prefix;
            prefix += count;
        }
        if (source_is_rows) {
            for (const Row<D>& row : rows) {
                Row<D>* const destination =
                    buffer +
                    offsets[
                        (get<0>(row) >> shift) & radix_mask]++;
                if (buffer_constructed)
                    *destination = row;
                else
                    allocator_traits_type::construct(
                        row_allocator, destination, row);
            }
            buffer_constructed = true;
        } else {
            for (size_t i = 0; i < rows.size(); ++i) {
                const Row<D>& row = buffer[i];
                rows[
                    offsets[
                        (get<0>(row) >> shift) & radix_mask]++] = row;
            }
        }

        source_is_rows = !source_is_rows;
        if ((maximum >> shift) < radix_size)
            break;
    }
    if (!source_is_rows)
        copy(buffer, buffer + rows.size(), rows.begin());
    for (size_t i = 0; i < rows.size(); ++i)
        allocator_traits_type::destroy(row_allocator, buffer + i);
    allocator_traits_type::deallocate(
        row_allocator, buffer, rows.size());
}

template <size_t D>
__attribute__((noinline, hot, section(".text.large"), optimize("O3")))
static void count_points_sorted(
    unsigned size, const unsigned* const* x) {
    vector<Row<D>> queries;
    queries.reserve(size + 1);
    for (unsigned i = 0; i < size; ++i)
        emplace_input_row<D>(queries, x, i);
    radix_sort_first<D>(queries, size);

    vector<Row<D - 1>> events;
    events.reserve(static_cast<size_t>(size) * 2);
    queries.emplace_back(make_sentinel<D>());
    unsigned point = 0;
    unsigned query = 0;
    for (unsigned remaining = size * 2; remaining; --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();

    static Workspace<D - 1>* workspace;
    if (!workspace)
        workspace = new Workspace<D - 1>(events.size());
    count_dynamic<D - 1>(events, *workspace, true);
}

template <size_t D>
__attribute__((noinline, hot)) static void count_points_counting(
    unsigned size, const unsigned* const* x, unsigned* out) {
    for (unsigned i = 0; i < size; ++i)
        ++out[x[0][i]];

    unsigned prefix = 0;
    for (unsigned value = 0; value < size; ++value) {
        const unsigned count = out[value];
        out[value] = prefix;
        prefix += count;
    }

    unique_ptr<unsigned[]> order(new unsigned[size]);
    for (unsigned i = 0; i < size; ++i)
        order[out[x[0][i]]++] = i;

    vector<Row<D - 1>> events;
    events.reserve(static_cast<size_t>(size) * 2);
    unsigned begin = 0;
    for (unsigned value = 0; value < size; ++value) {
        const unsigned end = out[value];
        out[value] = 0;
        for (unsigned position = begin; position < end; ++position) {
            const unsigned i = order[position];
            emplace_input_event<D>(events, x, i, i + 1);
        }
        for (unsigned position = begin; position < end; ++position)
            emplace_input_event<D>(events, x, order[position], 0);
        begin = end;
    }
    order.reset();

    static Workspace<D - 1>* workspace;
    if (!workspace)
        workspace = new Workspace<D - 1>(events.size());
    count_dynamic<D - 1>(events, *workspace);
}

template <size_t D>
__attribute__((always_inline)) static inline void
count_single_role_cross(
    vector<Row<D>>& rows,
    Workspace<D>& workspace,
    unsigned first_point,
    unsigned first_query,
    unsigned end_query) {
    if constexpr (D == 1) {
        count_static(
            rows, first_point, first_query, end_query);
    } else {
        const uint64_t pairs =
            static_cast<uint64_t>(
                first_query - first_point) *
            (end_query - first_query);
        if (pairs <= single_role_cross_pair_limit) {
            unsigned eligible_end = first_point;
            for (unsigned query = first_query;
                 query < end_query;
                 ++query) {
                while (eligible_end < first_query &&
                       get<0>(rows[eligible_end]) <
                           get<0>(rows[query]))
                    ++eligible_end;
                unsigned count = 0;
                for (unsigned point = first_point;
                     point < eligible_end;
                     ++point)
                    count += tail_coordinates_less<D>(
                        rows[point], rows[query]);
                *reinterpret_cast<unsigned*>(
                    answer_base +
                    sizeof(unsigned) *
                        get<D>(rows[query])) += count;
            }
            return;
        }

        vector<Row<D - 1>>& lower =
            workspace.lower.scratch;
        lower.clear();
        lower.reserve(end_query - first_point);
        unsigned point = first_point;
        unsigned query = first_query;
        while (point < first_query &&
               query < end_query) {
            if (get<0>(rows[query]) <=
                get<0>(rows[point])) {
                emplace_drop_first<D>(
                    lower,
                    rows[query],
                    get<D>(rows[query]));
                ++query;
            } else {
                emplace_drop_first<D>(
                    lower, rows[point], 0);
                ++point;
            }
        }
        while (point < first_query) {
            emplace_drop_first<D>(
                lower, rows[point], 0);
            ++point;
        }
        while (query < end_query) {
            emplace_drop_first<D>(
                lower,
                rows[query],
                get<D>(rows[query]));
            ++query;
        }
        count_dynamic<D - 1>(
            lower, workspace.lower);
    }
}

static unsigned choose_group_split(
    const vector<unsigned>& group_begin,
    unsigned first_group,
    unsigned end_group) {
    (void)group_begin;
    return (first_group + end_group) / 2;
}

template <size_t D, bool Root = false>
static void count_single_role_recursion(
    const vector<Row<D>>& input,
    Workspace<D>& workspace,
    const vector<unsigned>& group_begin,
    int output_id,
    unsigned first_group,
    unsigned end_group) {
    const unsigned l = group_begin[first_group];
    const unsigned r = group_begin[end_group];
    vector<Row<D>>& output =
        workspace.current.aux[output_id];
    if (end_group - first_group == 1) {
        copy(
            input.begin() + l,
            input.begin() + r,
            output.begin() + l);
        sort(output.begin() + l, output.begin() + r);
        return;
    }

    const unsigned middle_group =
        choose_group_split(
            group_begin, first_group, end_group);
    const unsigned m = group_begin[middle_group];
    count_single_role_recursion<D>(
        input,
        workspace,
        group_begin,
        !output_id,
        first_group,
        middle_group);
    count_single_role_recursion<D>(
        input,
        workspace,
        group_begin,
        !output_id,
        middle_group,
        end_group);

    vector<Row<D>>& children =
        workspace.current.aux[!output_id];
    count_single_role_cross<D>(
        children, workspace, l, m, r);
    if constexpr (!Root)
        merge(
            children.begin() + l,
            children.begin() + m,
            children.begin() + m,
            children.begin() + r,
            output.begin() + l);
}

template <size_t D>
__attribute__((always_inline)) static inline void count_points(
    int n, const unsigned* const* x, unsigned* out) {
    coordinate_bound = static_cast<unsigned>(n);
    answer_data = out;
    answer_base = reinterpret_cast<uintptr_t>(out) - sizeof(unsigned);
    const unsigned size = static_cast<unsigned>(n);
    dynamic_cross_pair_limit =
        size <= 100000
            ? 393216
            : (size <= 300000 ? 262144 : 65536);
    single_role_cross_pair_limit =
        size <= 300000 ? 131072 : 65536;
    if (size > 2000000) {
        count_points_sorted<D>(size, x);
        return;
    }
    memset(out, 0, sizeof(unsigned) * size);

    for (unsigned i = 0; i < size; ++i)
        ++out[x[0][i]];
    unsigned prefix = 0;
    for (unsigned value = 0; value < size; ++value) {
        const unsigned count = out[value];
        out[value] = prefix;
        prefix += count;
    }

    unique_ptr<unsigned[]> order(new unsigned[size]);
    for (unsigned i = 0; i < size; ++i)
        order[out[x[0][i]]++] = i;

    vector<Row<D - 1>> rows;
    rows.reserve(size);
    vector<unsigned> group_begin;
    group_begin.reserve(size + 1);
    group_begin.push_back(0);
    unsigned begin = 0;
    for (unsigned value = 0; value < size; ++value) {
        const unsigned end = out[value];
        out[value] = 0;
        if (begin < end) {
            if (begin)
                group_begin.push_back(begin);
            for (unsigned position = begin;
                 position < end;
                 ++position) {
                const unsigned point = order[position];
                emplace_input_event<D>(
                    rows, x, point, point + 1);
            }
        }
        begin = end;
    }
    group_begin.push_back(size);
    order.reset();

    static Workspace<D - 1>* workspace;
    if (!workspace)
        workspace = new Workspace<D - 1>(size);
    if (workspace->current.aux[0].size() < size)
        workspace->current.resize(size);
    count_single_role_recursion<D - 1, true>(
        rows,
        *workspace,
        group_begin,
        0,
        0,
        static_cast<unsigned>(
            group_begin.size() - 1));
}

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);
}

评测结果