代码

#pragma GCC target("avx2")

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <random>
#include <tuple>
#include <vector>
using namespace std;

static unsigned* out;

static void count_1d_static(vector<tuple<unsigned, unsigned>>& items, unsigned l, unsigned m, unsigned r) {
    unsigned i = l, cnt = 0;
    for (unsigned j = m; j < r; j++) {
        auto& [x, q] = items[j];
        while (i < m && get<0>(items[i]) < x)
            i++, cnt++;
        out[q] += cnt;
    }
}

template <bool Root = false>
static unsigned count_1d_dynamic_recursion(vector<tuple<unsigned, unsigned>>& items, unsigned l, unsigned r) {
    if (r - l <= 16) {
        for (unsigned i = l; i < r; i++)
            if (get<1>(items[i])) {
                unsigned tmp = 0;
                for (unsigned j = l; j < i; j++)
                    if (!get<1>(items[j]) && get<0>(items[j]) < get<0>(items[i]))
                        tmp++;
                out[get<1>(items[i])] += tmp;
            }
        sort(items.begin() + l, items.begin() + r, [](const auto& a, const auto& b) {
            if (!!get<1>(a) != !!get<1>(b))
                return !!get<1>(a) > !!get<1>(b);
            return a < b;
        });
        unsigned ret = l;
        while (ret < r && get<1>(items[ret]))
            ret++;
        return ret;
    }
    // queries, points
    if (r - l <= 1) {
        if (get<1>(items[l]))
            return r;
        else
            return l;
    }
    unsigned m = (l + r) / 2;
    unsigned lm = count_1d_dynamic_recursion(items, l, m);
    unsigned mr = count_1d_dynamic_recursion(items, m, r);
    count_1d_static(items, lm, m, mr);
    if (Root)
        return m;
    unsigned mq = mr - m + lm;
    rotate(items.begin() + lm, items.begin() + m, items.begin() + mr);
    inplace_merge(items.begin() + l, items.begin() + lm, items.begin() + mq);
    inplace_merge(items.begin() + mq, items.begin() + mr, items.begin() + r);
    return mq;
}

static void count_1d_dynamic(vector<tuple<unsigned, unsigned>>& items) {
    count_1d_dynamic_recursion<true>(items, 0, items.size());
}

static void count_2d_static_same(vector<tuple<unsigned, unsigned, unsigned>>& queries) {
    vector<tuple<unsigned, unsigned>> count_1d;
    int t = queries.size() * 2;
    count_1d.reserve(t);
    queries.emplace_back(-1, -1, 0);
    unsigned i = 0, j = 0;
    while (t--) {
        if (get<0>(queries[i]) < get<0>(queries[j])) {
            count_1d.emplace_back(get<1>(queries[i]), 0);
            i++;
        } else {
            count_1d.emplace_back(get<1>(queries[j]), get<2>(queries[j]));
            j++;
        }
    }
    count_1d_dynamic(count_1d);
    queries.pop_back();
}

void count_2d(int n, const unsigned *x, const unsigned *y, unsigned *out) {
    ::out = out - 1;
    vector<tuple<unsigned, unsigned, unsigned>> queries;
    queries.reserve(n);
    for (int i = 0; i < n; i++)
        queries.emplace_back(x[i], y[i], i + 1);
    sort(queries.begin(), queries.end());
    count_2d_static_same(queries);
}

static void count_2d_ref(int n, const unsigned *x, const unsigned *y, unsigned *out) {
    memset(out, 0, n * sizeof(unsigned));
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            if (x[i] < x[j] && y[i] < y[j])
                out[j]++;
}

int main() {
    cout << "generate" << endl;
    
    // int n = 10000;
    int n = 10000000;
    vector<unsigned> x(n), y(n);
    mt19937 rng(0);
    for (int i = 0; i < n; i++) {
        x[i] = rng() % n;
        y[i] = rng() % n;
    }

    vector<unsigned> out(n), out_ref(n);

    cout << "count_2d" << endl;
    count_2d(n, x.data(), y.data(), out.data());
    cout << "count_2d ok" << endl;

    // cout << "count_2d_ref" << endl;
    // count_2d_ref(n, x.data(), y.data(), out_ref.data());

    // cout << "check" << endl;
    // for (int i = 0; i < n; i++)
    //     if (out[i] != out_ref[i]) {
    //         printf("Wrong answer at %d: %u %u\n", i, out[i], out_ref[i]);
    //         return 1;
    //     }
    // printf("Correct answer\n");

    return 0;
}

评测结果