P3810 三维偏序

#include <bits/stdc++.h>
using namespace std;
const int N = 200100;
int n, k;
int sum[N], root[N], ans[N];
struct node {
    int l,r;//左子，右子
    int v,w;//节点的值，相同v的个数
    int rand;//随机值，用于维护堆
    int size; 
}t[N << 5];
int size = 0;
struct data {
    int a, b, c;
    friend bool operator == (const data &a, const data &b) {
        if(a.a != b.a || a.b != b.b || a.c != b.c) return false;
        return true;
    }
}f[N];
int lowbit(int x) {
    return x & (-x);
}

void updata(int x) {
    t[x].size = t[t[x].l].size + t[t[x].r].size + t[x].w;
}
void rturn(int &k)
{
    int tmp = t[k].l;
    t[k].l = t[tmp].r;
    t[tmp].r = k;
    t[tmp].size = t[k].size;
    updata(k);
    k = tmp;
}

void lturn(int &k) {
    int tmp = t[k].r;
    t[k].r = t[tmp].l;
    t[tmp].l = k;
    t[tmp].size = t[k].size;
    updata(k);
    k = tmp;
}

void insert(int &k,int x) {
    if(!k)//当前点为空，分配一个
    {
        k = ++size;
        t[k].size = t[k].w = 1;
        t[k].v = x;
        t[k].rand = rand();
        return; 
    }

    t[k].size++;
    if(t[k].v == x) t[k].w++;
    else if(x < t[k].v) {
        insert(t[k].l,x);
        if(t[t[k].l].rand < t[k].rand) rturn(k);
    }
    else {
        insert(t[k].r,x);
        if(t[t[k].r].rand < t[k].rand) lturn(k);
    } 
}

int rnk(int k,int x)//查询x的排名
{
    if(!k)
        return 0;
    if(x == t[k].v)
        return t[k].w + t[t[k].l].size;
    else if(x < t[k].v)
        return rnk(t[k].l,x);
    else
        return t[k].w + t[t[k].l].size + rnk(t[k].r,x);
}

bool cmp(data a,data b) {
    if(a.a != b.a) return a.a < b.a;
    if(a.b != b.b) return a.b < b.b;
    return a.c < b.c;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> k;
    for(int i = 1; i <= n; i++)
    cin >> f[i].a >> f[i].b >> f[i].c;

    sort(f + 1, f + n + 1, cmp);

    int sit;
    for(int i = 1; i <= n; i++)
    {
        if(f[i] == f[i + 1] && i != n) sum[i + 1] = sum[i] + 1;
        else
        {
            sit = 0;
            for(int j = f[i].b; j > 0; j -= lowbit(j)) //减lowbit，向b小于b[i]的元素统计排名的和，即b小于b[i]元素中c小于c[i]的元素个数
            sit += rnk(root[j], f[i].c);

            ans[sit] += sum[i] + 1;
        }
        for(int j = f[i].b; j <= k; j += lowbit(j)) //加lowbit，向b[i]所在的节点的平衡树添加c[i]
        insert(root[j], f[i].c);
    }

    for(int i = 0; i < n; i++)
    cout << ans[i] << '\n';
    return 0;
}