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

小咪咪 2023-08-17 17:21 71阅读 0赞

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

[题目传送门][Link 1]

## 解题思路 ##

用的CDQ分治。先以a为第一关键字，b为第二关键字，c为第三关键字从小到大排序。然后以b为关键字按照从小到大的顺序进行归并排序，在归并排序时，用树状数组来维护c。但是这样只能计算前面的元素对后面的元素的贡献，当存在相等的元素时就会漏算，所以在归并前先将相同的合并，对于合并的内部另外算贡献即可。

## 代码如下 ##

#include <bits/stdc++.h> using namespace std; const int N = 200005; struct T{ int i, a, b, c, e; T(){} T(int a, int b, int c, int e): a(a), b(b), c(c), e(e){} bool operator<(const T& r)const{ if(a != r.a) return a < r.a; else if(b != r.b) return b < r.b; else return c < r.c; } }v[N], t[N]; int n, k; int c[N]; int lowbit(int x) { return x & (-x); } void update(int x, int v) { for(int i = x; i <= k; i += lowbit(i)) c[i] += v; } int query(int x) { int ans = 0; for(int i = x; i > 0; i -= lowbit(i)) ans += c[i]; return ans; } int f[N], ans[N]; void CDQ(int l, int r) { if(l == r) return; int mid = (l + r) / 2; CDQ(l, mid); CDQ(mid + 1, r); for(int i = l; i <= r; i ++) t[i] = v[i]; int x = l, y = mid + 1; int cnt = l - 1; while(x <= mid || y <= r){ if(x <= mid && y <= r){ if(t[x].b <= t[y].b){ update(t[x].c, t[x].e); v[++cnt] = t[x]; ++x; } else { f[t[y].i] += query(t[y].c); v[++cnt] = t[y]; ++y; } } else if(x <= mid){ update(t[x].c, t[x].e); v[++cnt] = t[x]; ++x; } else { f[t[y].i] += query(t[y].c); v[++cnt] = t[y]; ++y; } } for(int i = l; i <= mid; i ++) update(t[i].c, -t[i].e); } int main() { scanf("%d%d", &n, &k); for(int i = 1; i <= n; i ++){ int a, b, c; scanf("%d%d%d", &a, &b, &c); v[i] = T(a, b, c, 1); } sort(v + 1, v + n + 1); int cnt = 1; v[1].i = 1; for(int i = 2; i <= n; i ++){ if(v[i].a == v[cnt].a && v[i].b == v[cnt].b && v[i].c == v[cnt].c) v[cnt].e ++; else { v[++cnt] = v[i]; v[cnt].i = cnt; } } CDQ(1, cnt); sort(v + 1, v + cnt + 1); for(int i = 1; i <= cnt; i ++) ans[f[i] + v[i].e - 1] += v[i].e; for(int i = 0; i < n; i ++) printf("%d\n", ans[i]); return 0; }

转载于:https://www.cnblogs.com/whisperlzw/p/11545337.html

[Link 1]: https://www.luogu.org/problem/P3810