首页

陌上花开，可缓缓归矣 —— 吴越王

P3810 【模板】三维偏序（陌上花开）

# 二维偏序 - 归并排序求逆序对

P1908 逆序对

直接扔个板子好了：

#include <cstdio>
#include <iostream>
#define rep(i,s,t) for(int i=s;i<=t;i++)
#define mid (l+r)>>1
using namespace std;
using ll = long long;
const int MAXN = 5e5 + 233;
int n, a[MAXN], t[MAXN];
ll ans;
void mergeSort(int l, int r)
{
    if (l == r)
        return;
    int m = mid;
    mergeSort(l, m);
    mergeSort(m + 1 , r);
    int p = l, q = m + 1, s = l;
    while (p <= m && q <= r)
        if (a[p] > a[q])
        {
            t[s++] = a[q++];
            ans += m - p + 1;
        }
        else
            t[s++] = a[p++];
    while (p <= m)
        t[s++] = a[p++];
    while (q <= r)
        t[s++] = a[q++];
    rep (i, l, r)
        a[i] = t[i];
}
int main()
{
    scanf("%d", &n);
    rep (i, 1, n)
        scanf("%d", &a[i]);
    mergeSort(1, n);
    printf("%lld\n", ans);
	return 0;
}

# 三维偏序 - CDQ 分治 + BIT

# CDQ 分治

一种思想，就分治嘛..（跟线段树啊，归并排序啊什么的都有点像 emm）

Fake Code:

void cdq(int l, int r)
{
    if (l == r) return;
    int m = (l + r) >> 1;
    cdq(l, m); cdq(m + 1, r);
    /**
    * 做些什么合并左右区间
    */
    return;
}

# 陌上花开

# 题目描述

三维偏序经典问题：

竟然找不到原题面了真可惜 qwq，，算法竞赛选手不配学语文呜呜呜咱最会爬了 QAQ

题目大意：

有一堆花，每朵花有三个属性 ai,bi,cia_i, b_i, c_i 。

对于每一朵花 ii ，认为它比另一朵花 jj 漂亮，当且仅当 aj≤ai&&bj≤bi&&cj≤cia_j \leq a_i \quad \&\& \quad b_j \leq b_i \quad \&\& \quad c_j \leq c_i 。

每朵花 ii 有一个等级，一朵花的等级是它的美丽 能超过的花的数量。

求每个等级的花有多少。

# 输入输出格式

输入 n, k 表示花朵数和最大属性值，接下来每行是一朵花的 a, b, c 三个属性。

n 范围 1e5， k 范围 2e5。

分行输出 0 ~ n - 1 等级花朵个数。

# 思路

先按 a 排序，再拿这组数据对 b 做归并排序， 合并的时候用树状数组维护一下 c，查询记录答案即可。

由于多次处理重复元素会出事，提前进行一下去重，记录重复次数什么的 emm

# 代码

#include <cstdio>
#include <iostream>
#include <algorithm>
#define rep(i,s,t) for(int i=s;i<=t;i++)
#define mid (l+r)>>1
using namespace std;
const int MAXN = 1e5 + 233;
int n, k, N;
struct node
{
	int a, b, c;
	int cnt, ans; // 重复次数，等级（不含相同的花）
} arr[MAXN], tmparr[MAXN];
int tre[MAXN << 1], ans[MAXN];
bool operator == (node& xx, node& yy)
{
	return (yy.a == xx.a) && (yy.b == xx.b) && (yy.c == xx.c);
}
int lb(int x)
{
	return x & (-x);
}
void add(int x, int v)
{
	for (; x <= k; x += lb(x))
		tre[x] += v;
}
int query(int x)
{
	int sum = 0;
	for (; x; x -= lb(x))
		sum += tre[x];
	return sum;
}
bool cmp1(node& xx, node& yy)
{
	return xx.a != yy.a ? xx.a < yy.a : xx.b != yy.b ? xx.b < yy.b : xx.c < yy.c;
}
void cdq(int l, int r)
{
	if (l == r) return;
	int m = mid;
	cdq(l, m);
	cdq(m + 1, r);
	int p = l, q = m + 1, s = l;
	while (p <= m && q <= r)
	{
		if (arr[p].b <= arr[q].b)
		{
			add(arr[p].c, arr[p].cnt); //b 条件符合，把 c 扔进树状数组里统计
			tmparr[s++] = arr[p++];
		}
		else
		{
			arr[q].ans += query(arr[q].c); //b 条件符合，从树状数组里查询 c
			tmparr[s++] = arr[q++];
		}
	}
	while (q <= r)
	{
		arr[q].ans += query(arr[q].c);
		tmparr[s++] = arr[q++];
	}
	rep (i, l, p - 1)
		add(arr[i].c, -arr[i].cnt); // 记得清空树状数组
	while (p <= m)
		tmparr[s++] = arr[p++];
	rep (i, l, r)
		arr[i] = tmparr[i];
}
int main()
{
	scanf("%d%d", &n, &k);
	rep (i, 1, n)
		scanf("%d%d%d", &tmparr[i].a, &tmparr[i].b, &tmparr[i].c);
	sort(tmparr + 1, tmparr + n + 1, cmp1);
    // 去重
	rep (i, 1, n)
	{
		int j = i + 1;
		while (tmparr[j] == tmparr[j - 1] && j <= n)
			j++;
		arr[++N] = tmparr[i];
		arr[N].cnt = j - i;
		i = j - 1; // 这里炸掉一次 qwq
	}
	cdq(1, N); // 这里炸掉一次，是 N 不是 n，qwq
	rep (i, 1, N)
        //ans [等级] += 重复次数，记录每个等级花朵个数
    	// 相同的花，每一朵都比其它相同的要漂亮，所以每一朵的等级都要加上 cnt - 1
		ans[arr[i].ans + arr[i].cnt - 1] += arr[i].cnt;
	rep (i, 0, n - 1)
		printf("%d\n", ans[i]);
	return 0;
}
更新于