代码

#pragma GCC target("avx2")

#include <algorithm>
#include <tuple>
#include <vector>
using namespace std;

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

static auto count_1d_dynamic_recursion(const vector<tuple<unsigned, unsigned*>>& items, unsigned l, unsigned r) {
    pair<vector<tuple<unsigned>>, vector<tuple<unsigned, unsigned*>>> ans;
    auto& [points, queries] = ans;
    if (r - l <= 1) {
        if (get<1>(items[l]))
            queries.emplace_back(items[l]);
        else
            points.emplace_back(get<0>(items[l]));
        return ans;
    }
    unsigned m = (l + r) / 2;
    auto [left_points, left_queries] = count_1d_dynamic_recursion(items, l, m);
    auto [right_points, right_queries] = count_1d_dynamic_recursion(items, m, r);
    count_1d_static(left_points, right_queries);
    points.reserve(left_points.size() + right_points.size());
    queries.reserve(left_queries.size() + right_queries.size());
    merge(left_points.begin(), left_points.end(), right_points.begin(), right_points.end(), back_inserter(points));
    merge(left_queries.begin(), left_queries.end(), right_queries.begin(), right_queries.end(), back_inserter(queries));
    return ans;
}

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

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

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

评测结果