代码

#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, vector<tuple<unsigned, unsigned>>* aux, int id, unsigned l, unsigned r) {
    // queries, points
    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;
        });
        copy(items.begin() + l, items.begin() + r, aux[id].begin() + l);
        unsigned ret = l;
        while (ret < r && get<1>(items[ret]))
            ret++;
        return ret;
    }
    unsigned m = (l + r) / 2;
    unsigned lm = count_1d_dynamic_recursion(items, aux, !id, l, m);
    unsigned mr = count_1d_dynamic_recursion(items, aux, !id, m, r);
    count_1d_static(aux[!id], lm, m, mr);
    if (Root)
        return -1;
    unsigned mq = mr - m + lm;
    merge(aux[!id].begin() + l, aux[!id].begin() + lm, aux[!id].begin() + m, aux[!id].begin() + mr, aux[id].begin() + l);
    merge(aux[!id].begin() + lm, aux[!id].begin() + m, aux[!id].begin() + mr, aux[!id].begin() + r, aux[id].begin() + mq);
    return mq;
}

static void count_1d_dynamic(vector<tuple<unsigned, unsigned>>& items) {
    vector<tuple<unsigned, unsigned>> aux[2];
    aux[0].resize(items.size());
    aux[1].resize(items.size());
    count_1d_dynamic_recursion<true>(items, aux, 0, 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 + 1);
    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);
}

评测结果