题意
给出 n 个元素，每个元素有三个属性 a ,b ,c。
定义 f(i) 表示 \(a_j \leq a_i\ and\ b_j\leq b_i\ and\ c_j\leq c_i\) 的 j 的个数。
对于 \(d\epsilon[0,n)\),求 f(i)==d 的个数。
思路
CDQ分治。
首先我们按照 \(a\) 的从小到大排序。
对于一个区间 \([l,r]\)：
假如此时我们已经处理完了区间 \([l,mid]\) 以及 区间\([mid+1,r]\) 里的所有个数；
那么现在就剩下一个点在 \([l,mid]\) 一个点在 \([mid+1,r]\) 里的情况没有统计。
因为 \(a\) 值是从小到大排序的，所以我们在统计最后一种情况的时候不用考虑 \(a\) 的大小。
现在还有两个限制条件 \(b_i\leq b_j\ and\ c_i\leq c_j\)。
我们将 \([l,mid] \ and \ [mid+1,r]\) 中的元素按照 \(b\) 值从小到大排序。
枚举 \(j\) 的值，把 \(b_i\leq b_j\) 的\(c_i\) 放到树状数组中，来查询有多少个 \(c\) 小于等于 \(c_j\)。
我们使用双指针的方式来进行更新以及查询。
因为题目中可能有相同的元素所以要去重，最后加上相同元素产生的贡献
代码
#include <algorithm>
#include <iostream>
#include <map>
#include <math.h>
#include <queue>
#include <set>
#include <stack>
#include <stdio.h>
#include <string.h>
#include <string>
#include <vector>
#define emplace_back push_back
#define pb push_back
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int mod = 1e9 + 7;
const int seed = 12289;
const double eps = 1e-6;
const int inf = 0x3f3f3f3f;
const int N = 2e5 + 10;
struct note {
int a, b, c, cnt, ans;
} arr[N], brr[N];
int cnt[N];
bool cmp1(note x, note y)
{
if (x.a == y.a) {
if (x.b == y.b)
return x.c < y.c;
return x.b < y.b;
}
return x.a < y.a;
}
bool cmp2(note x, note y)
{
if (x.b == y.b) {
return x.c < y.c;
}
return x.b < y.b;
}
struct treearray {
int tree[N], k; //k表示最大值
int lowbit(int x)
{
return x & (-x);
}
void update(int pos, int x)
{
for (; pos <= k; pos += lowbit(pos)) {
tree[pos] += x;
}
}
int sum(int pos)
{
int ans = 0;
for (; pos; pos -= lowbit(pos)) {
ans += tree[pos];
}
return ans;
}
} tr;
void cdq(int l, int r)
{
if (l == r)
return;
int mid = (l + r) / 2;
cdq(l, mid), cdq(mid + 1, r);
sort(brr + l, brr + mid + 1, cmp2);
sort(brr + mid + 1, brr + r + 1, cmp2);
int i = l, j = mid + 1;
for (; j <= r; j++) {
while (brr[i].b <= brr[j].b && i <= mid) {
tr.update(brr[i].c, brr[i].cnt);
i++;
}
brr[j].ans += tr.sum(brr[j].c);
}
for (j = l; j < i; j++) {
tr.update(brr[j].c, -brr[j].cnt);
}
}
int main()
{
int n;
scanf("%d%d", &n, &tr.k);
for (int i = 1; i <= n; i++) {
scanf("%d%d%d", &arr[i].a, &arr[i].b, &arr[i].c);
}
sort(arr + 1, arr + 1 + n, cmp1);
int m = 1;
brr[1].a = arr[1].a, brr[1].b = arr[1].b, brr[1].c = arr[1].c, brr[1].cnt = 1;
for (int i = 2; i <= n; i++) {
if (arr[i].a == arr[i - 1].a && arr[i].b == arr[i - 1].b && arr[i].c == arr[i - 1].c) {
brr[m].cnt++;
continue;
}
brr[++m].a = arr[i].a, brr[m].b = arr[i].b, brr[m].c = arr[i].c, brr[m].cnt = 1;
}
cdq(1, m);
for (int i = 1; i <= m; i++) {
cnt[brr[i].ans + brr[i].cnt - 1] += brr[i].cnt;
}
for (int i = 0; i < n; i++) {
printf("%d\n", cnt[i]);
}
return 0;
}