CDQ套树状数组解三维偏序

3262: 陌上花开

三维偏序：

给定N个有序三元组(a,b,c)，求对于每个三元组(a,b,c)，有多少个三元组(a2,b2,c2)满足a2<a且b2<b且c2<c。

　　不用CDQ分治的方法：先按照a元素排序，从左到右扫描。按照b元素构造权值树状数组，树状数组每个节点按照c元素构造平衡树。树套树的解法不仅常数大，而且代码量巨大，还容易写错。

　　类似二维偏序问题，先按照a元素从小到大排序，忽略a元素的影响。然后CDQ分治，按照b元素从大到小的顺序进行归并操作。但是这时候没办法像 求逆序对 一样简单地统计 个数 了，c元素如何处理呢？

　　这时候比较好的方案就是借助权值树状数组。我们先把左边的集合全部丢进树状数组里面，每次从右边的序列中取出三元组(a,b,c)时，对树状数组查询c值小于(a,b,c)的三元组有多少个；每次从左边序列取出三元组(a,b,c)的时候，根据c值在树状数组中进行删除。

        记得把相同的三元组进行合并处理。

//#include<bits/stdc++.h>
//#include<unordered_map>
//#include<unordered_set>
#include<iostream>
#include<sstream>
#include<iterator>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<set>
#include<vector>
#include<bitset>
#include<climits>
#include<queue>
#include<iomanip>
#include<cmath>
#include<stack>
#include<map>
#include<ctime>
#include<new>
using namespace std;
#define LL long long
#define ULL unsigned long long
#define MT(a, b) memset(a,b,sizeof(a))
const int INF
=
0x3f3f3f3f;
const int O
=
1e6;
const int mod
=
1e6+7;
const int maxn =
5e5 +5;
const double PI
=
acos(-1.0);
const double E
=
2.718281828459;
const double eps = 1e-8;
struct dd {int x, y, z, num, lx;
bool friend operator < (dd a, dd b) {
return a.x == b.x ?
(a.y == b.y ? a.z < b.z : a.y < b.y) : a.x < b.x;
}
} a[maxn], b[maxn];
int c[maxn];
int n, k;
#define lowbit(x) x & (-x)
void add(int pos, int x) {
while(pos <= k) { c[pos] += x; pos += lowbit(pos); }
}
int sum(int pos ) {
int ans = 0;
while(pos > 0) { ans += c[pos]; pos -= lowbit(pos); }
return ans;
}
void cdq (int l, int r) {
if(l == r) return ;
int mid = (l + r) >> 1;
cdq(l, mid );
cdq(mid + 1, r);
int ql = l, qr = mid + 1;
for(int i=l; i<=mid; i++) add(a[i].z, a[i].num);
for(int i=l; i<=r; i++){
if( (ql <= mid && a[ql].y > a[qr].y) || qr > r) {
add( a[ql].z, -a[ql].num );
b[i] = a[ql ++];
}
else {
a[qr].lx += sum (a[qr].z);
b[i] = a[qr ++];
}
}
for(int i=l; i<=r; i++) a[i] = b[i];
}
int
ans[maxn];
int main(){
scanf("%d%d", &n, &k);
for(int i=0; i<n; i++) scanf("%d%d%d", &a[i].x, &a[i].y, &a[i].z);
sort(a, a + n);
int cnt = 0, num = 1;
for(int i=1; i<=n; i++) {
if(a[i].x == a[i-1].x && a[i].y == a[i-1].y && a[i].z == a[i-1].z) num ++;
else {
a[cnt] = a[i-1]; a[cnt ++].num = num; num = 1;
}
}
cdq(0, cnt - 1);
for(int i=0; i<cnt; i++) ans[ a[i].lx + a[i].num - 1 ] += a[i].num;
for(int i=0; i<n; i++) printf("%dn", ans[i]);
return 0;
}

最后

以上就是幽默红牛为你收集整理的CDQ套树状数组解三维偏序的全部内容，希望文章能够帮你解决CDQ套树状数组解三维偏序所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。