洛谷 P3810 【模板】三维偏序(陌上花开)
2022/9/10 6:55:35
本文主要是介绍洛谷 P3810 【模板】三维偏序(陌上花开),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
原题链接
第一维直接排序,然后cdq分治+树状数组
对于分治的左右区间,区间内部按照第二维排序(已按第一维排序好了,就算打乱顺序,左右区间整体的第一维的偏序关系也不会受到影响)
然后遍历右区间的元素,把左区间的第二维小于当前元素的加入树状数组,统计答案即可,因为区间内部第二维都是单调不递减的,只需遍历一遍
#include<bits/stdc++.h> using namespace std; #define fr first #define se second #define et0 exit(0); #define rep(i, a, b) for(int i = (int)(a); i <= (int)(b); i ++) #define rrep(i, a, b) for(int i = (int)(a); i >= (int)(b); i --) #define IO ios::sync_with_stdio(false),cin.tie(0); typedef long long LL; typedef pair<int, int> PII; typedef pair<LL, LL> PLL; typedef unsigned long long ULL; const int INF = 0X3f3f3f3f, N = 2e5 + 10, MOD = 1e9 + 7; const double eps = 1e-7, pi = acos(-1); int n, k; struct NODE{ int x, y, z, cnt, res; }a[N], b[N]; bool cmp1(NODE &A, NODE &B) { if (A.x == B.x) { if (A.y == B.y) return A.z < B.z; return A.y < B.y; } return A.x < B.x; } bool cmp2(NODE &A, NODE &B) { if (A.y == B.y) return A.z < B.z; return A.y < B.y; } int tr[N]; int lowbit(int x){ return x & -x; } void insert(int x, int c){ for(int i = x; i <= k; i += lowbit(i)) tr[i] += c; } int query(int x){ int res = 0; for(int i = x; i >= 1; i -= lowbit(i)) res += tr[i]; return res; } void cdq(int l, int r) { if (l == r) return; int mid = l + r >> 1; cdq(l, mid), cdq(mid + 1, r); sort(b + l, b + mid + 1, cmp2); sort(b + mid + 1, b + r + 1, cmp2); int tt = l; rep (i, mid + 1, r) { while (tt <= mid && b[i].y >= b[tt].y) { insert(b[tt].z, b[tt].cnt); tt++; } b[i].res += query(b[i].z); } rep (i, l, tt - 1) insert(b[i].z, -b[i].cnt); } void work() { cin >> n >> k; rep (i, 1, n) cin >> a[i].x >> a[i].y >> a[i].z; sort(a + 1, a + 1 + n, cmp1); int count = 0; rep (i, 1, n) { if (a[i].x != b[count].x || a[i].y != b[count].y || a[i].z != b[count].z) { count++; b[count].x = a[i].x, b[count].y = a[i].y, b[count].z = a[i].z; b[count].cnt = 1; } else b[count].cnt++; } cdq(1, count); vector<int> ans(n + 1); rep (i, 1, count) ans[b[i].res + b[i].cnt - 1] += b[i].cnt; rep (i, 0, n - 1) cout << ans[i] << endl; } signed main() { IO int test = 1; while (test--) { work(); } return 0; }
这篇关于洛谷 P3810 【模板】三维偏序(陌上花开)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-01为什么公共事业机构会偏爱 TiDB :TiDB 数据库在某省妇幼健康管理系统的应用
- 2024-04-26敏捷开发:想要快速交付就必须舍弃产品质量?
- 2024-04-26静态代码分析的这些好处,我竟然都不知道?
- 2024-04-26你在测试金字塔的哪一层?(下)
- 2024-04-26快刀斩乱麻,DevOps让代码评审也自动起来
- 2024-04-262024年最好用的10款ER图神器!
- 2024-04-2203-为啥大模型LLM还没能完全替代你?
- 2024-04-2101-大语言模型发展
- 2024-04-17基于SpringWeb MultipartFile文件上传、下载功能
- 2024-04-14个人开发者,Spring Boot 项目如何部署