代码

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

const int MAXN = 300005;

struct Point {
    unsigned a[5];
    int id;
};

// 用于四维CDQ的临时结构
struct Node4 {
    unsigned a[4];
    int id, flag; // flag: 0表示左半，1表示右半
};

// 用于三维CDQ的临时结构
struct Node3 {
    unsigned a[3];
    int id, flag;
};

// 用于二维CDQ的临时结构
struct Node2 {
    unsigned a[2];
    int id, flag;
};

class Fenwick {
    int n;
    vector<int> bit;
public:
    Fenwick(int n = 0) { init(n); }
    void init(int n_) { 
        n = n_;
        bit.assign(n + 1, 0);
    }
    void add(int idx, int val) {
        for (++idx; idx <= n; idx += idx & -idx) bit[idx] += val;
    }
    int sum(int idx) {
        int res = 0;
        for (++idx; idx > 0; idx -= idx & -idx) res += bit[idx];
        return res;
    }
    void clear() {
        fill(bit.begin(), bit.end(), 0);
    }
};

int n;
vector<Point> points;
unsigned *out_global;

// 第四层CDQ：处理二维偏序 (x3, x4)
void cdq4(vector<Node2>& nodes, int l, int r, Fenwick& bit) {
    if (l >= r) return;
    int mid = (l + r) >> 1;
    cdq4(nodes, l, mid, bit);
    cdq4(nodes, mid + 1, r, bit);
    
    // 处理左半对右半的贡献
    int i = l, j = mid + 1;
    vector<Node2> tmp;
    while (i <= mid && j <= r) {
        if (nodes[i].a[0] < nodes[j].a[0]) {
            if (nodes[i].flag == 0) {
                bit.add(nodes[i].a[1], 1);
            }
            tmp.push_back(nodes[i++]);
        } else {
            if (nodes[j].flag == 1) {
                out_global[nodes[j].id] += bit.sum(nodes[j].a[1] - 1);
            }
            tmp.push_back(nodes[j++]);
        }
    }
    while (i <= mid) {
        if (nodes[i].flag == 0) {
            bit.add(nodes[i].a[1], 1);
        }
        tmp.push_back(nodes[i++]);
    }
    while (j <= r) {
        if (nodes[j].flag == 1) {
            out_global[nodes[j].id] += bit.sum(nodes[j].a[1] - 1);
        }
        tmp.push_back(nodes[j++]);
    }
    
    // 清除树状数组
    for (int k = l; k <= mid; ++k) {
        if (nodes[k].flag == 0) {
            bit.add(nodes[k].a[1], -1);
        }
    }
    
    for (int k = l; k <= r; ++k) {
        nodes[k] = tmp[k - l];
    }
}

// 第三层CDQ：处理三维偏序 (x2, x3, x4)
void cdq3(vector<Node3>& nodes, int l, int r, Fenwick& bit) {
    if (l >= r) return;
    int mid = (l + r) >> 1;
    cdq3(nodes, l, mid, bit);
    cdq3(nodes, mid + 1, r, bit);
    
    // 构建第四层的节点
    vector<Node2> nodes4;
    for (int i = l; i <= mid; ++i) {
        Node2 nd;
        nd.a[0] = nodes[i].a[1];
        nd.a[1] = nodes[i].a[2];
        nd.id = nodes[i].id;
        nd.flag = 0; // 左半
        nodes4.push_back(nd);
    }
    for (int i = mid + 1; i <= r; ++i) {
        Node2 nd;
        nd.a[0] = nodes[i].a[1];
        nd.a[1] = nodes[i].a[2];
        nd.id = nodes[i].id;
        nd.flag = 1; // 右半
        nodes4.push_back(nd);
    }
    
    // 按 x3 排序
    sort(nodes4.begin(), nodes4.end(), [](const Node2& a, const Node2& b) {
        if (a.a[0] != b.a[0]) return a.a[0] < b.a[0];
        return a.a[1] < b.a[1];
    });
    
    cdq4(nodes4, 0, nodes4.size() - 1, bit);
    bit.clear();
    
    // 合并排序
    int i = l, j = mid + 1;
    vector<Node3> tmp;
    while (i <= mid && j <= r) {
        if (nodes[i].a[0] < nodes[j].a[0]) {
            tmp.push_back(nodes[i++]);
        } else {
            tmp.push_back(nodes[j++]);
        }
    }
    while (i <= mid) tmp.push_back(nodes[i++]);
    while (j <= r) tmp.push_back(nodes[j++]);
    for (int k = l; k <= r; ++k) {
        nodes[k] = tmp[k - l];
    }
}

// 第二层CDQ：处理四维偏序 (x1, x2, x3, x4)
void cdq2(vector<Node4>& nodes, int l, int r, Fenwick& bit) {
    if (l >= r) return;
    int mid = (l + r) >> 1;
    cdq2(nodes, l, mid, bit);
    cdq2(nodes, mid + 1, r, bit);
    
    // 构建第三层的节点
    vector<Node3> nodes3;
    for (int i = l; i <= mid; ++i) {
        Node3 nd;
        nd.a[0] = nodes[i].a[1];
        nd.a[1] = nodes[i].a[2];
        nd.a[2] = nodes[i].a[3];
        nd.id = nodes[i].id;
        nd.flag = 0;
        nodes3.push_back(nd);
    }
    for (int i = mid + 1; i <= r; ++i) {
        Node3 nd;
        nd.a[0] = nodes[i].a[1];
        nd.a[1] = nodes[i].a[2];
        nd.a[2] = nodes[i].a[3];
        nd.id = nodes[i].id;
        nd.flag = 1;
        nodes3.push_back(nd);
    }
    
    // 按 x2 排序
    sort(nodes3.begin(), nodes3.end(), [](const Node3& a, const Node3& b) {
        if (a.a[0] != b.a[0]) return a.a[0] < b.a[0];
        if (a.a[1] != b.a[1]) return a.a[1] < b.a[1];
        return a.a[2] < b.a[2];
    });
    
    cdq3(nodes3, 0, nodes3.size() - 1, bit);
    bit.clear();
    
    // 合并排序
    int i = l, j = mid + 1;
    vector<Node4> tmp;
    while (i <= mid && j <= r) {
        if (nodes[i].a[0] < nodes[j].a[0]) {
            tmp.push_back(nodes[i++]);
        } else {
            tmp.push_back(nodes[j++]);
        }
    }
    while (i <= mid) tmp.push_back(nodes[i++]);
    while (j <= r) tmp.push_back(nodes[j++]);
    for (int k = l; k <= r; ++k) {
        nodes[k] = tmp[k - l];
    }
}

// 第一层CDQ：处理五维偏序 (x0, x1, x2, x3, x4)
void cdq1(vector<Point>& pts, int l, int r, Fenwick& bit) {
    if (l >= r) return;
    int mid = (l + r) >> 1;
    cdq1(pts, l, mid, bit);
    cdq1(pts, mid + 1, r, bit);
    
    // 构建第二层的节点
    vector<Node4> nodes4;
    for (int i = l; i <= mid; ++i) {
        Node4 nd;
        for (int d = 0; d < 4; ++d) nd.a[d] = pts[i].a[d + 1];
        nd.id = pts[i].id;
        nd.flag = 0;
        nodes4.push_back(nd);
    }
    for (int i = mid + 1; i <= r; ++i) {
        Node4 nd;
        for (int d = 0; d < 4; ++d) nd.a[d] = pts[i].a[d + 1];
        nd.id = pts[i].id;
        nd.flag = 1;
        nodes4.push_back(nd);
    }
    
    // 按 x1 排序
    sort(nodes4.begin(), nodes4.end(), [](const Node4& a, const Node4& b) {
        if (a.a[0] != b.a[0]) return a.a[0] < b.a[0];
        if (a.a[1] != b.a[1]) return a.a[1] < b.a[1];
        if (a.a[2] != b.a[2]) return a.a[2] < b.a[2];
        return a.a[3] < b.a[3];
    });
    
    cdq2(nodes4, 0, nodes4.size() - 1, bit);
    bit.clear();
    
    // 合并排序（按x0）
    int i = l, j = mid + 1;
    vector<Point> tmp;
    while (i <= mid && j <= r) {
        if (pts[i].a[0] < pts[j].a[0]) {
            tmp.push_back(pts[i++]);
        } else {
            tmp.push_back(pts[j++]);
        }
    }
    while (i <= mid) tmp.push_back(pts[i++]);
    while (j <= r) tmp.push_back(pts[j++]);
    for (int k = l; k <= r; ++k) {
        pts[k] = tmp[k - l];
    }
}

// 主函数
void count_5d(int n, const unsigned *x[5], unsigned *out) {
    ::n = n;
    out_global = out;
    
    points.resize(n);
    for (int i = 0; i < n; ++i) {
        for (int d = 0; d < 5; ++d) {
            points[i].a[d] = x[d][i];
        }
        points[i].id = i;
        out[i] = 0;
    }
    
    // 按x0排序
    sort(points.begin(), points.end(), [](const Point& a, const Point& b) {
        if (a.a[0] != b.a[0]) return a.a[0] < b.a[0];
        if (a.a[1] != b.a[1]) return a.a[1] < b.a[1];
        if (a.a[2] != b.a[2]) return a.a[2] < b.a[2];
        if (a.a[3] != b.a[3]) return a.a[3] < b.a[3];
        return a.a[4] < b.a[4];
    });
    
    Fenwick bit(n + 5);
    cdq1(points, 0, n - 1, bit);
}

评测结果