【CDQ分治】三维偏序（luogu 3801/金牌导航 CDQ分治-1）

本文主要是介绍【CDQ分治】三维偏序（luogu 3801/金牌导航 CDQ分治-1），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

三维偏序

luogu 3801

金牌导航 CDQ分治-1

题目大意

有n个元素，第i个元素有 $a_i,b_i,c_i$ 三个属性，设 f(i)表示满足 $a_j\leqslant a_i$ 且 $b_j \leqslant b_i$ 且 $c_j \leqslant c_i$ 且 $\ne i$ 的j的数量
对于 $\in [0, n)$ ，求 f(i) = d的数量

样例输入

样例输出

数据范围

$1\leqslant N\leqslant 10^5,1\leqslant a_i,b_i,c_i\leqslant k\leqslant 2\times10^5$

解题思路

先对第一维进行排序然后在分治的同时归并排序，并求出左子树中b值比右子树大的，对于第三维，用树状数组计算即可

代码

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
#define N 100010
using namespace std;
int n, k, g, c[N<<1], ans[N];
struct node
{int a, b, c, v, s;
}a[N], b[N];
bool cmpp(node a, node b)
{return a.b < b.b;
}
bool cmp(node a, node b)
{return a.a < b.a || a.a == b.a && a.b < b.b || a.a == b.a && a.b == b.b && a.c < b.c;
}
void add(int x, int y)
{for (; x <= k; x += x & -x)c[x] += y;
}
int ask(int x)
{int sum = 0;for (; x; x -= x & -x)sum += c[x];return sum;
}
void solve(int l, int r)
{if (l == r) return;int mid = l + r >> 1, h1 = l, h2 = mid + 1, h = l;solve(l, mid);//分治solve(mid + 1, r);while(h1 <= mid && h2 <= r)//归并排序，同时用树状数组求答案{if (a[h1].b <= a[h2].b){add(a[h1].c, a[h1].s);b[h++] = a[h1++];}else{a[h2].v += ask(a[h2].c);b[h++] = a[h2++];}}while(h1 <= mid){add(a[h1].c, a[h1].s);b[h++] = a[h1++];}while(h2 <= r){a[h2].v += ask(a[h2].c);b[h++] = a[h2++];}for (int i = l; i <= mid; ++i)add(a[i].c, -a[i].s);for (int i = l; i <= r; ++i)a[i] = b[i];
}
int main()
{scanf("%d%d", &n, &k);for (int i = 1; i <= n; ++i)scanf("%d%d%d", &a[i].a, &a[i].b, &a[i].c);sort(a + 1, a + 1 + n, cmp);a[g = 1].s++;for (int i = 2; i <= n; ++i)if (a[g].a == a[i].a && a[g].b == a[i].b && a[g].c == a[i].c) a[g].s++;//离散化else a[++g] = a[i], a[g].s++;solve(1, g);for (int i = 1; i <= g; ++i)ans[a[i].v + a[i].s - 1] += a[i].s;//还要加上相等但不是同一个点的值for (int i = 0; i < n; ++i)printf("%d\n", ans[i]);return 0;
}