代码

#pragma GCC target("avx2")

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

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

template <size_t D>
struct Row {
    unsigned values[D + 1];
#ifdef POD_ROW_TRACK_INITIALIZATION
    bool initialized;
#endif
};

static_assert(is_trivial<Row<1>>::value);
static_assert(is_trivially_copyable<Row<1>>::value);
static_assert(is_standard_layout<Row<1>>::value);

template <size_t I, size_t D>
__attribute__((always_inline)) static inline unsigned get(
    const Row<D>& row) {
#ifdef POD_ROW_TRACK_INITIALIZATION
    assert(row.initialized);
#endif
    return row.values[I];
}

template <size_t I, size_t D>
__attribute__((always_inline)) static inline unsigned& get(Row<D>& row) {
#ifdef POD_ROW_TRACK_INITIALIZATION
    assert(row.initialized);
#endif
    return row.values[I];
}

template <size_t I, size_t D>
__attribute__((always_inline)) static inline bool row_less_impl(
    const Row<D>& a, const Row<D>& b) {
    if constexpr (I == D + 1) {
        return false;
    } else {
        const unsigned av = get<I>(a);
        const unsigned bv = get<I>(b);
        return av < bv ||
               (av == bv && row_less_impl<I + 1>(a, b));
    }
}

template <size_t D>
__attribute__((always_inline)) static inline bool operator<(
    const Row<D>& a, const Row<D>& b) {
    return row_less_impl<0>(a, b);
}

template <class T>
struct UninitializedBuffer {
    unique_ptr<T[]> storage;
    size_t logical_size = 0;
    size_t capacity = 0;

    UninitializedBuffer() = default;

    UninitializedBuffer(const UninitializedBuffer&) = delete;
    UninitializedBuffer& operator=(const UninitializedBuffer&) = delete;

    __attribute__((always_inline)) void reserve(size_t n) {
        if (capacity < n || !storage) {
            const size_t allocation = n ? n : 1;
            storage.reset(new T[allocation]);
            capacity = allocation;
        }
    }

    __attribute__((always_inline)) void resize(size_t n) {
        reserve(n);
        logical_size = n;
    }

    __attribute__((always_inline)) size_t size() const {
        return logical_size;
    }

    __attribute__((always_inline)) T* begin() {
        return storage.get();
    }

    __attribute__((always_inline)) const T* begin() const {
        return storage.get();
    }

    __attribute__((always_inline)) T& operator[](size_t i) {
        return storage[i];
    }

    __attribute__((always_inline)) const T& operator[](size_t i) const {
        return storage[i];
    }

#ifdef POD_ROW_TRACK_INITIALIZATION
    void reset_initialization(size_t n) {
        assert(n <= capacity);
        for (size_t i = 0; i < n; ++i)
            storage[i].initialized = false;
    }

    void assert_initialized(size_t l, size_t r) const {
        assert(r <= capacity);
        for (size_t i = l; i < r; ++i)
            assert(storage[i].initialized);
    }
#endif
};

template <size_t D>
struct Buffers {
    UninitializedBuffer<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);
    }

#ifdef POD_ROW_TRACK_INITIALIZATION
    void reset_initialization(size_t n) {
        aux[0].reset_initialization(n);
        aux[1].reset_initialization(n);
    }
#endif
};

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, class... Values>
__attribute__((always_inline)) static inline Row<D> make_row(
    Values... values) {
    static_assert(sizeof...(Values) == D + 1);
    Row<D> row{{static_cast<unsigned>(values)...}
#ifdef POD_ROW_TRACK_INITIALIZATION
               ,
               true
#endif
    };
    return row;
}

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(make_row<D - 1>(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(make_row<D - 1>(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(make_row<D>(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 make_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>
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, class Rows>
static inline void count_static(
    Rows& 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);
}

template <class Rows>
static inline void count_static(
    Rows& 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 constexpr uint64_t direct_cross_pair_limit = 65536;

template <size_t D, class Rows>
__attribute__((always_inline)) static inline void count_cross(
    Rows& 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 <= direct_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;
        UninitializedBuffer<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);
#ifdef POD_ROW_TRACK_INITIALIZATION
        output.assert_initialized(l, r);
#endif
        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);
#ifdef POD_ROW_TRACK_INITIALIZATION
    workspace.current.aux[id].assert_initialized(l, r);
#endif
    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);
#ifdef POD_ROW_TRACK_INITIALIZATION
    workspace.current.reset_initialization(r);
#endif
    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>
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];

    unique_ptr<Row<D>[]> buffer(new Row<D>[rows.size()]);
    bool source_is_rows = true;
    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)
                buffer[
                    offsets[
                        (get<0>(row) >> shift) & radix_mask]++] = row;
        } 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.get(), buffer.get() + rows.size(), rows.begin());
}

template <size_t D>
__attribute__((noinline, hot)) 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_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);
    if (size > 2000000)
        count_points_sorted<D>(size, x);
    else {
        memset(out, 0, sizeof(unsigned) * n);
        count_points_counting<D>(size, x, out);
    }
}

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

评测结果