专栏文章

cdq^k：k 维偏序

SSkyWave
算法·理论参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mip0luaq
此快照首次捕获于
2025/12/03 04:12
3 个月前
此快照最后确认于
2025/12/03 04:12
3 个月前
查看原文
这是一份我原创的 kk 维偏序模板，实现了一个名为 kDPO 的模板结构体，代码如下：

代码实现

CPP
template <typename Tp, int K>
struct kDPO {
	const vector<array<Tp, K>> &arr;
	
	kDPO(const vector<array<Tp, K>> &arr_) : arr(arr_) {
		
	}
	
	vector<int> a, cnt, ans, hero;
	array<vector<int>, K - 2> b;
	void cdq(int l, int r) {
		if (l == r) {
			return ;
		}
		
		int mid = (l + r) >> 1;
		cdq(l, mid);
		cdq(mid + 1, r);
		
		int i = l, j = mid + 1;
		if constexpr (K == 2) {
			int sum = 0;
			hero.clear();
			while (i <= mid || j <= r) {
				if (j > r || (i <= mid && arr[a[i]][1] <= arr[a[j]][1])) {
					++sum;
					hero.emplace_back(a[i]);
					++i;
				} else {
					ans[a[j]] += sum;
					hero.emplace_back(a[j]);
					++j;
				}
			}
			memcpy(a.data() + l, hero.data(), sizeof(int) * (r - l + 1));
		} else {
			b[0].clear();
			while (i <= mid || j <= r) {
				if (j > r || (i <= mid && arr[a[i]][1] <= arr[a[j]][1])) {
					b[0].push_back(a[i]);
					++i;
				} else {
					b[0].push_back(a[j] | 1 << 31);
					++j;
				}
			}
			for (int i = 0; i < r - l + 1; ++i) {
				a[i + l] = b[0][i] & 2147483647;
			}
			
			cdq(0, r - l, 0);
		}
	}
	void cdq(int l, int r, int d) {
		if (l == r) {
			return ;
		}
		
		int mid = (l + r) >> 1;
		cdq(l, mid, d);
		cdq(mid + 1, r, d);
		
		int i = l, j = mid + 1;
		hero.clear();
		if (d == K - 3) {
			int sum = 0;
			while (i <= mid || j <= r) {
				if (j > r || (i <= mid && arr[b[d][i] & 2147483647][K - 1] <= arr[b[d][j] & 2147483647][K - 1])) {
					sum += b[d][i] >> 31 ? 0 : cnt[b[d][i] & 2147483647];
					hero.emplace_back(b[d][i]);
					++i;
				} else {
					ans[b[d][j] & 2147483647] += b[d][j] >> 31 ? sum : 0;
					hero.emplace_back(b[d][j]);
					++j;
				}
			}
			memcpy(b[d].data() + l, hero.data(), sizeof(int) * (r - l + 1));
			return ;
		}
		b[d + 1].clear();
		while (i <= mid || j <= r) {
			if (j > r || (i <= mid && arr[b[d][i] & 2147483647][d + 2] <= arr[b[d][j] & 2147483647][d + 2])) {
				if (!(b[d][i] >> 31)) {
					b[d + 1].push_back(b[d][i]);
				}
				hero.emplace_back(b[d][i]);
				++i;
			} else {
				if (b[d][j] >> 31) {
					b[d + 1].push_back(b[d][j]);
				}
				hero.emplace_back(b[d][j]);
				++j;
			}
		}
		memcpy(b[d].data() + l, hero.data(), sizeof(int) * (r - l + 1));
		
		if (!b[d + 1].empty()) {
			cdq(0, (int)b[d + 1].size() - 1, d + 1);
		}
	}
	
	vector<int> operator () () {
		int n = (int)arr.size();
		
		vector<int> ord(n);
		iota(ord.begin(), ord.end(), 0);
		sort(ord.begin(), ord.end(), [&](int x, int y) {
			return arr[x] < arr[y];
		});
		
		vector<pair<int, int>> equa;
		equa.reserve(n);
		cnt.resize(n);
		for (int i = 0; i < n; ) {
			int j = i + 1;
			for ( ; j < n && arr[ord[j]] == arr[ord[i]]; ++j) {
				equa.emplace_back(ord[j], ord[i]);
			}
			
			a.emplace_back(ord[i]);
			cnt[ord[i]] = j - i;
			
			i = j;
		}
		ans.resize(n);
		hero.reserve(n);
		for (vector<int> &i : b) {
			i.reserve(n);
		}
		
		cdq(0, (int)a.size() - 1);
		
		for (int i = 0; i < n; ++i) {
			ans[i] += cnt[i] - 1;
		}
		for (pair<int, int> i : equa) {
			ans[i.first] = ans[i.second];
		}
		return ans;
	}
};
template <typename Tp>
struct kDPO<Tp, 1> {
	const vector<array<Tp, 1>> &arr;
	
	kDPO(const vector<array<Tp, 1>> &arr_) : arr(arr_) {
		
	}
	
	vector<int> operator () () const {
		int n = (int)arr.size();
		
		vector<int> ord(n);
		iota(ord.begin(), ord.end(), 0);
		sort(ord.begin(), ord.end(), [&](int x, int y) {
			return arr[x] < arr[y];
		});
		
		vector<int> ans(n);
		for (int i = 0; i < n; ) {
			int j = i + 1;
			for ( ; j < n && arr[ord[j]] == arr[ord[i]]; ++j);
			
			for ( ; i < j; ++i) {
				ans[ord[i]] = j - 1;
			}
		}
		return ans;
	}
};

签名讲解

代码有点长，我也写了很久，优化了更久！
我先来讲解一下 kDPO 以及它的 operator () 的签名。
kDPO 的构造函数只接受一个 const vector<array<Tp, k>> &arr，设 nn 为 arr.size()。arrarr 描述了 nn 个有 kk 维属性的元素，属性的类型为 Tp，arr[i][0],arr[i][1],…,arr[i][k−1]arr[i][0], arr[i][1], \dots, arr[i][k - 1], 依次描述了 kk 维属性的值。
调用 kDPO 的 operator () 即开始求解 kk 维偏序。t它的时间复杂度为 O(nklog⁡n+nlog⁡k−1n)O(nk \log n + n \log^{k-1} n)，空间复杂度为 Θ(nk)\Theta(nk)。它返回一个长度为 nn 的 vector<int>，设其名为 ans，则 ans[i] 为 arr[i] 偏序不同于它的元素的个数。形式化的： ans[i]=(∑j=0n−1[⋀l=0k−1arr[j][l]≤arr[i][l]])−1ans[i] = \left(\sum_{j=0}^{n-1} \left[\bigwedge_{l=0}^{k-1} arr[j][l] \leq arr[i][l]\right]\right) - 1

示例

对于经典题目 P3810 【模板】三维偏序（陌上花开）:
CPP
#include <bits/stdc++.h>
using namespace std;

template <typename Tp, int K>
struct kDPO {

};

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int n, k;
	cin >> n >> k;
	vector<array<int, 3>> arr(n);
	for (array<int, 3> &i : arr) {
		for (int &j : i) {
			cin >> j;
		}
	}
	vector<int> res = kDPO<int, 3>(arr)(), ans(n);
	for (int i : res) {
		++ans[i];
	}
	for (int i : ans) {
		cout << i << '\n';
	}
	return 0;
}
表现：提交记录

k 为变量

CPP
template <typename Tp>
struct kDPO<Tp, 0> {
	const vector<vector<Tp>> &arr;
	int k;
	
	kDPO(const vector<vector<Tp>> &arr_) : arr(arr_) {
		k = arr[0].size();
	}
	
	vector<int> a, cnt, ans;
	vector<vector<int>> b;
	vector<int> hero;
	void cdq(int l, int r) {
		if (l == r) {
			return ;
		}
		
		int mid = (l + r) >> 1;
		cdq(l, mid);
		cdq(mid + 1, r);
		
		int i = l, j = mid + 1;
		b[0].clear();
		while (i <= mid || j <= r) {
			if (j > r || (i <= mid && arr[a[i]][1] <= arr[a[j]][1])) {
				b[0].push_back(a[i]);
				++i;
			} else {
				b[0].push_back(a[j] | 1 << 31);
				++j;
			}
		}
		for (int i = 0; i < r - l + 1; ++i) {
			a[i + l] = b[0][i] & 2147483647;
		}
		
		cdq(0, r - l, 0);
	}
	void cdq(int l, int r, int d) {
		if (l == r) {
			return ;
		}
		
		int mid = (l + r) >> 1;
		cdq(l, mid, d);
		cdq(mid + 1, r, d);
		
		int i = l, j = mid + 1;
		hero.clear();
		if (d == k - 3) {
			int sum = 0;
			while (i <= mid || j <= r) {
				if (j > r || (i <= mid && arr[b[d][i] & 2147483647][k - 1] <= arr[b[d][j] & 2147483647][k - 1])) {
					sum += b[d][i] >> 31 ? 0 : cnt[b[d][i] & 2147483647];
					hero.emplace_back(b[d][i]);
					++i;
				} else {
					ans[b[d][j] & 2147483647] += b[d][j] >> 31 ? sum : 0;
					hero.emplace_back(b[d][j]);
					++j;
				}
			}
			memcpy(b[d].data() + l, hero.data(), sizeof(int) * (r - l + 1));
			return ;
		}
		b[d + 1].clear();
		while (i <= mid || j <= r) {
			if (j > r || (i <= mid && arr[b[d][i] & 2147483647][d + 2] <= arr[b[d][j] & 2147483647][d + 2])) {
				if (!(b[d][i] >> 31)) {
					b[d + 1].push_back(b[d][i]);
				}
				hero.emplace_back(b[d][i]);
				++i;
			} else {
				if (b[d][j] >> 31) {
					b[d + 1].push_back(b[d][j]);
				}
				hero.emplace_back(b[d][j]);
				++j;
			}
		}
		memcpy(b[d].data() + l, hero.data(), sizeof(int) * (r - l + 1));
		
		if (!b[d + 1].empty()) {
			cdq(0, (int)b[d + 1].size() - 1, d + 1);
		}
	}
	
	vector<int> operator () () {
		int n = (int)arr.size();
		if (k == 1) {
			vector<array<Tp, 1>> a(n);
			for (int i = 0; i < n; ++i) {
				a[i][0] = arr[i][0];
			}
			return kDPO<Tp, 1>(a)();
		}
		if (k == 2) {
			vector<array<Tp, 2>> a(n);
			for (int i = 0; i < n; ++i) {
				a[i][0] = arr[i][0];
				a[i][1] = arr[i][1];
			}
			return kDPO<Tp, 2>(a)();
		}		
		
		vector<int> ord(n);
		iota(ord.begin(), ord.end(), 0);
		sort(ord.begin(), ord.end(), [&](int x, int y) {
			return arr[x] < arr[y];
		});
		
		vector<pair<int, int>> equa;
		equa.reserve(n);
		cnt.resize(n);
		for (int i = 0; i < n; ) {
			int j = i + 1;
			for ( ; j < n && arr[ord[j]] == arr[ord[i]]; ++j) {
				equa.emplace_back(ord[j], ord[i]);
			}
			
			a.emplace_back(ord[i]);
			cnt[ord[i]] = j - i;
			
			i = j;
		}
		ans.resize(n);
		hero.reserve(n);
		b.resize(k - 2);
		for (vector<int> &i : b) {
			i.reserve(n);
		}
		
		cdq(0, (int)a.size() - 1);
		
		for (int i = 0; i < n; ++i) {
			ans[i] += cnt[i] - 1;
		}
		for (pair<int, int> i : equa) {
			ans[i.first] = ans[i.second];
		}
		return ans;
	}
};

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...