隐藏
「bzoj3262」陌上花开 - CDQ分治三维偏序 | Bill Yang's Blog

路终会有尽头,但视野总能看到更远的地方。

0%

「bzoj3262」陌上花开 - CDQ分治三维偏序

题目大意

维护三维偏序,统计有$i$个比当前点大的点有多少个。


三维偏序普适框架

维护三维偏序使用CDQ分治解决。
CDQ分治是什么?请参考这里
在这里我们提出一种不需要在CDQ中排序的方法,普适性强,常数更小。
初学者请先使用排序的方法,更容易理解,再接受本文方法。


我们首先按照$y$维排序(当然也可以按照$x$排序,将下文的$x$、$y$交换),然后进行CDQ分治。

CDQ分治时我们将区间中$x$维$\le mid$的值放在左边,将$x$维$\ge mid$的值放在右边。
可以发现,此时我们将$x$较小的放在了左边,较大的放在了右边,分割线为$mid$,且左右区间$y$均有序。

1
2
3
4
5
int mid=(Left+Right)>>1,lpos=Left,rpos=mid+1;
for(int i=Left; i<=Right; i++) //按照mid分割第一维
if(a[i].x<=mid)tmp[lpos++]=a[i];
else tmp[rpos++]=a[i];
for(int i=Left; i<=Right; i++)a[i]=tmp[i];

是否注意到这份代码有点问题?
若$x$值有相等的,那么区间分割线根本不是$mid$,而且上述代码有致命的问题。
没错,的确有这个问题,因为如果$x$值有相等的,我们根本无法进行CDQ。
如果我们强行用$mid$拆分可能导致左右大小划分不清,若按照$x$把相等的分在一起,可能会导致时间效率大幅度降低。
因此我们必须保证$x$互不相同。

因为此时左右区间的$y$分别仍然有序,因此我们可以立刻递归左子树。

1
CDQBianry(Left,mid);

接下来处理左边对右边的影响。
我们还是用以前的方法,双指针维护$y$的有序性,按照$z$添加树状数组。

1
2
3
4
5
6
7
8
int j=Left;
for(int i=mid+1; i<=Right; i++) { //bit维护第三维
while(j<=mid&&a[j].y<=a[i].y) {
bit.add(a[j].z,a[j].cnt);
j++;
}
a[i].ans+=bit.sum(a[i].z);
}

接下来清空树状数组并递归右子树。

1
2
for(int i=Left; i<=mid; i++)bit.clear(a[i].z);
CDQBianry(mid+1,Right);

此时就可以结束了吗?不能,因为此时我们已经破坏了当前区间的$y$维有序性,递归到上一层将会导致$z$值无法维护。
如下图:

因此我们还需要重新对$y$进行排序。怎么办,这不就要用到sort了?别着急,这是两个$y$的有序表,双指针维护有序表合并是$O(n)$的,可以用STL直接实现。

1
2
3
int tot=0;
merge(a+Left,a+mid+1,a+mid+1,a+Right+1,tmp,cmp);
for(int i=Left; i<=Right; i++)a[i]=tmp[tot++];


初步想法

虽然说此题是一道维护三维偏序的题,但是有很多细节。
比如题目说了:两朵花可能有同样的属性
但是我们刚刚才说了CDQ的那一维必须互不相同,怎么办呢?

我们可以强行对$x$维“离散化”,首先我们把完全相同的花合并成一朵花,这样就没有完全相同的花了。
但是$x$维重复元素并没有解决,怎么办呢?刚刚我们已经排除了完全相同的花,那么剩下的花一定互不相同,我们就可以排序后对$x$重新编一个互不相同的编号,即可使得$x$互不相同。

另外注意我们将相同的花变成了一朵花,故需要CDQ时对相同的花也累加进入答案。


代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
const int maxn=100005,maxv=200005;
int n,k;
struct BIT {
int c[maxv];
#define lowbit(x) x&(-x)
void add(int x,int v) {
for(int i=x; i<=k; i+=lowbit(i))c[i]+=v;
}
void clear(int x) {
for(int i=x; i<=k; i+=lowbit(i))c[i]=0;
}
int sum(int x) {
int sum=0;
for(int i=x; i>=1; i-=lowbit(i))sum+=c[i];
return sum;
}
} bit;
struct Flower {
int x,y,z,cnt,ans;
Flower(int _x=0,int _y=0,int _z=0,int t=0):x(_x),y(_y),z(_z),cnt(t),ans(0) {}
bool operator < (const Flower& b) const {
return x<b.x||(x==b.x&&y<b.y)||(x==b.x&&y==b.y&&z<b.z);
}
} a[maxn],tmp[maxn];
bool cmp(const Flower& a,const Flower& b) {
return a.y<b.y||(a.y==b.y&&a.z<b.z)||(a.y==b.y&&a.z==b.z&&a.x<b.x);
}
void CDQBianry(int Left,int Right) {
if(Left==Right) {
a[Left].ans+=a[Left].cnt-1;
return;
}
int mid=(Left+Right)>>1,lpos=Left,rpos=mid+1;
for(int i=Left; i<=Right; i++) //按照mid分割第一维
if(a[i].x<=mid)tmp[lpos++]=a[i];
else tmp[rpos++]=a[i];
for(int i=Left; i<=Right; i++)a[i]=tmp[i];
CDQBianry(Left,mid);
int j=Left;
for(int i=mid+1; i<=Right; i++) { //bit维护第三维
while(j<=mid&&a[j].y<=a[i].y) {
bit.add(a[j].z,a[j].cnt);
j++;
}
a[i].ans+=bit.sum(a[i].z);
}
for(int i=Left; i<=mid; i++)bit.clear(a[i].z);
CDQBianry(mid+1,Right);
int tot=0;
merge(a+Left,a+mid+1,a+mid+1,a+Right+1,tmp,cmp);
for(int i=Left; i<=Right; i++)a[i]=tmp[tot++];
}
int cnt[maxn];
int main() {
n=Get_Int();
k=Get_Int();
for(int i=1; i<=n; i++) {
int x=Get_Int(),y=Get_Int(),z=Get_Int();
a[i]=Flower(x,y,z,1);
}
sort(a+1,a+n+1);
int j=1;
for(int i=2; i<=n; i++) { //去重
if(a[i].x==a[j].x&&a[i].y==a[j].y&&a[i].z==a[j].z)a[j].cnt++;
else a[++j]=a[i];
}
int tmp=n;
n=j;
for(int i=1; i<=n; i++)a[i].x=i;
sort(a+1,a+n+1,cmp);
CDQBianry(1,n);
for(int i=1; i<=n; i++)cnt[a[i].ans]+=a[i].cnt;
for(int i=0; i<tmp; i++)printf("%d\n",cnt[i]);
return 0;
}

另外此题还可以使用树套树,此处不详细叙述,可以使用树状数组套平衡树实现,代码量略长:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
const int maxn=1000005;
struct Tree {
int father,child[2]; //0左儿子 1右儿子
int key,cnt,size; //key为结点属性 cnt是出现次数 size为子树大小
Tree() {}
Tree(int fa,int lc,int rc,int data,int tot,int sz):father(fa),key(data),cnt(tot),size(sz) {
child[0]=lc,child[1]=rc;
}
};
int n,m,root[maxn];
struct Splay {
int size;
Tree tree[maxn];
inline void init() {
size=0;
memset(tree,0,sizeof(tree));
}
inline void clear(int index) {
tree[index]=Tree(0,0,0,0,0,0);
}
inline int checkson(int index) { //判断是父亲的左儿子还是右儿子
return tree[tree[index].father].child[1]==index;
}
inline void update(int index) { //更新size
if(!index)return;
tree[index].size=tree[index].cnt;
if(tree[index].child[0])tree[index].size+=tree[tree[index].child[0]].size;
if(tree[index].child[1])tree[index].size+=tree[tree[index].child[1]].size;
}
inline void rotate(int index) { //旋转到根
int father=tree[index].father,grandpa=tree[father].father,side=checkson(index);
tree[father].child[side]=tree[index].child[side^1];
tree[tree[father].child[side]].father=father;
tree[father].father=index;
tree[index].child[side^1]=father;
tree[index].father=grandpa;
if(grandpa)tree[grandpa].child[tree[grandpa].child[1]==father]=index;
update(father);
update(index);
}
inline void splay(int& root,int index) {
if(index==root)return;
for(int father; (father=tree[index].father); rotate(index)) //基本旋转
if(tree[father].father)rotate((checkson(index)==checkson(father))?father:index); //附加旋转
root=index;
}
inline void insert(int& root,int v) { //传过来编号
int now=root,father=0;
while(true) {
if(tree[now].key==v) { //重复元素
tree[now].cnt++;
update(now);
update(father);
splay(root,now);
break;
}
father=now; //保存父亲
now=tree[now].child[tree[now].key<v]; //往哪边走
if(!now) {
tree[++size]=Tree(father,0,0,v,1,1);
if(root)tree[father].child[tree[father].key<v]=size;
update(father);
splay(root,size);
break;
}
}
}
inline int Find(int& root,int v) {
if(root==0)return 0;
if(v==tree[root].key)return tree[tree[root].child[0]].size+tree[root].cnt;
else if(v<tree[root].key)return Find(tree[root].child[0],v);
else return tree[tree[root].child[0]].size+tree[root].cnt+Find(tree[root].child[1],v);
}
} bbt;
struct BIT { //树状数组
inline int Lowbit(int x) { //低位操作
return x&(-x);
}
inline void add(int a,int b) {
for(int i=a; i<=m; i+=Lowbit(i))bbt.insert(root[i],b);
}
inline int sum(int a,int b) { //求出1~x的区间和
int s=0;
for(int i=a; i; i-=Lowbit(i))s+=bbt.Find(root[i],b);
return s;
}
} bit;
struct Flower {
int s,c,m;
bool operator < (const Flower& b) const {
return s<b.s||(s==b.s&&c<b.c)||(s==b.s&&c==b.c&&m<b.m);
}
} a[maxn];
int Ans[maxn],Delta=0;
int main() {
n=Get_Int();
m=Get_Int();
for(int i=1; i<=n; i++) {
a[i].s=Get_Int();
a[i].c=Get_Int();
a[i].m=Get_Int();
}
sort(a+1,a+n+1);
for(int i=1; i<=n; i++) {
if(a[i].s==a[i+1].s&&a[i].c==a[i+1].c&&a[i].m==a[i+1].m)Delta++;
else {
int ans=bit.sum(a[i].c,a[i].m);
Ans[ans]+=Delta+1;
Delta=0;
}
bit.add(a[i].c,a[i].m);
}
for(int i=0; i<n; i++)printf("%d\n",Ans[i]);
return 0;
}

姥爷们赏瓶冰阔落吧~