隐藏
「福建wc2014」3D桌球 - CDQ分治三维偏序 | Bill Yang's Blog

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

0%

「福建wc2014」3D桌球 - CDQ分治三维偏序

题目大意

求出三维偏序的最长序列长度。(偏序指各个维度对应单调)


CDQ分治简介

维护三维偏序,CDQ分治经典应用。
CDQ分治的思想:
我们在网上搜索CDQ分治的学习资料时都大同小异,大概都是说先递归左边,计算左边信息对右边的影响,再递归右边。
实际上这确实是CDQ分治的思想,但是就这么一句话并不能使新学CDQ分治的同学们理解。
在这里我先总结一下CDQ分治解决偏序问题的思路,CDQ分治可以解决很多问题,等我以后整理学习笔记吧。


CDQ分治解决偏序问题

请注意,使用CDQ分治解决偏序问题只能解决非严格不等号,若严格不等处理起来非常麻烦。

一维偏序问题

去重后输出总数即可

二维偏序问题

对一维排序,对另一维求一个LIS即可。

三维偏序问题

这就要用到CDQ了,首先我们对一维排序,比如对第一维排序。
在第二维我们不断的二分区间,就像下面这一个图:

因为我们是求一个类似LIS的东西,所以说应该根据第一维从左往右递推。在CDQ分治中如何实现呢?这就等价于不断地先递归左子区间。

请初学者不要想象整个CDQ分治递归的过程,只关注当前层,父亲层,儿子层。

假设递归左子区间已经完成,那么我们考虑维护当前的LIS,我们在CDQ之前已经保证了第一维的单调性,那么左子区间的第一维一定是相对于右子区间单调的。(也就是说,左子区间的第一维$\le$或$\ge$右子区间的第一维)
那么我们只需要保证第二维单调,就可以在第三维上使用树状数组做LIS了,CDQ分治的作用就是使第二维单调。

刚刚我们已经说了左子区间的第一维$\le$或$\ge$右子区间的第一维,那么我们可以直接对左/右子区间按照第二维排序。
那么显然,左子区间的第一维还是$\le$或$\ge$右子区间的第一维,而左/右子区间内部的第二维单调。
现在我们维护两个指针分别指向两个子区间,初始时指针指在区间首位置。

将$i$指针第二维比$j$指针第二维小的全部加入LIS,然后维护$j$指针处的三维偏序答案即可,这个应该不需要细讲,看代码即可。
我们相当于用排序、CDQ分治、树状数组各维护了一维偏序。

处理完后我们清空树状数组,再对右子区间按照第一维排序(因为我们刚刚按照第二维排序打乱了原来的顺序需要还原)。

接着再递归右区间即可。
可以发现CDQ分治始终是以左边更新右边,且更新右边时左边一定处理完毕,所以我们可以不重复不遗漏地统计完答案。

是不是觉得很神奇?将无序转成有序,这就是CDQ分治的作用,当然需要离线,时间复杂度$O(n\log^2n)$。

四维偏序问题

使用二重CDQ分治+树状数组维护。
二重CDQ即CDQ嵌套,与线段树套线段树写法类似。
这类题目比较少见,时间复杂度$O(n\log^3n)$。


初步想法

树状数组维护LIS的同时维护一下方案数即可。


代码

下方有update

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
#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=50005,mod=1000000007;
struct Ball {
int x,y,z,pos;
bool operator < (const Ball& b) const {
return x<b.x||(x==b.x&&y<b.y)||(x==b.x&&y==b.y&&z<b.z);
}
} a[maxn];
bool cmp(const Ball& a,const Ball& b) {
return a.y<b.y||(a.y==b.y&&a.z<b.z);
}
int n,f[maxn],g[maxn],ans1=0,ans2=0;
struct BIT {
int c[maxn],gc[maxn];
#define lowbit(x) x&(-x)
void add(int x,int pos) {
for(int i=x; i<=n; i+=lowbit(i))
if(f[pos]>c[i]) {
c[i]=f[pos];
gc[i]=g[pos];
} else if(f[pos]==c[i])gc[i]=(gc[i]+g[pos])%mod;
}
void clear(int x) {
for(int i=x; i<=n; i+=lowbit(i))c[i]=gc[i]=0;
}
void ask(int x,int pos) {
for(int i=x; i>=1; i-=lowbit(i)) {
if(f[pos]<c[i]+1) {
f[pos]=c[i]+1;
g[pos]=gc[i];
} else if(f[pos]==c[i]+1)g[pos]=(g[pos]+gc[i])%mod;
}
}
} bit;
void CDQBinary(int Left,int Right) {
if(Left==Right)return;
int mid=(Left+Right)>>1;
CDQBinary(Left,mid);
sort(a+Left,a+mid+1,cmp);
sort(a+mid+1,a+Right+1,cmp);
int j=Left;
for(int i=mid+1; i<=Right; i++) {
while(j<=mid&&a[j].y<=a[i].y) {
bit.add(a[j].z,a[j].pos);
j++;
}
bit.ask(a[i].z,a[i].pos);
}
for(int i=Left; i<=mid; i++)bit.clear(a[i].z);
sort(a+mid+1,a+Right+1);
CDQBinary(mid+1,Right);
}
int b[maxn],c[maxn];
void Discretization(int* a) {
memcpy(b,a,sizeof(b));
sort(a+1,a+n+1);
int cnt=unique(a+1,a+n+1)-a-1;
for(int i=1; i<=n; i++)b[i]=lower_bound(a+1,a+cnt+1,b[i])-a;
}
int main() {
n=Get_Int();
for(int i=1; i<=n; i++) {
a[i].x=Get_Int();
a[i].y=Get_Int();
a[i].z=Get_Int();
a[i].pos=i;
f[i]=g[i]=1;
c[i]=a[i].z;
}
Discretization(c);
for(int i=1; i<=n; i++)a[i].z=b[i];
sort(a+1,a+n+1);
CDQBinary(1,n);
for(int i=1; i<=n; i++) {
if(f[i]>ans1) {
ans1=f[i];
ans2=g[i];
} else if(f[i]==ans1)ans2=(ans2+g[i])%mod;
}
printf("%d %d\n",ans1,ans2);
return 0;
}

update(2017.9.22):
本方法因为在CDQ过程中使用了快排,会使常数增加。
我们可以使用划分和归并的思想完成CDQ。
当然这种方法需要对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
99
100
101
102
103
104
105
106
107
108
109
110
111
#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=50005,mod=1000000007;
struct Ball {
int x,y,z,pos;
bool operator < (const Ball& 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 Ball& a,const Ball& 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);
}
int n,f[maxn],g[maxn],ans1=0,ans2=0;
struct BIT {
int c[maxn],gc[maxn];
#define lowbit(x) x&(-x)
void add(int x,int pos) {
for(int i=x; i<=n; i+=lowbit(i))
if(f[pos]>c[i]) {
c[i]=f[pos];
gc[i]=g[pos];
} else if(f[pos]==c[i])gc[i]=(gc[i]+g[pos])%mod;
}
void clear(int x) {
for(int i=x; i<=n; i+=lowbit(i))c[i]=gc[i]=0;
}
void ask(int x,int pos) {
for(int i=x; i>=1; i-=lowbit(i)) {
if(f[pos]<c[i]+1) {
f[pos]=c[i]+1;
g[pos]=gc[i];
} else if(f[pos]==c[i]+1)g[pos]=(g[pos]+gc[i])%mod;
}
}
} bit;
void CDQBinary(int Left,int Right) {
if(Left==Right)return;
int mid=(Left+Right)>>1;
int lst=Left,rst=mid+1;
for(int i=Left; i<=Right; i++)
if(a[i].y<=mid)tmp[lst++]=a[i];
else tmp[rst++]=a[i];
for(int i=Left; i<=Right; i++)a[i]=tmp[i];
CDQBinary(Left,mid);
int j=Left;
for(int i=mid+1; i<=Right; i++) {
while(j<=mid&&a[j]<a[i]) {
bit.add(a[j].z,a[j].pos);
j++;
}
bit.ask(a[i].z,a[i].pos);
}
for(int i=Left; i<=mid; i++)bit.clear(a[i].z);
CDQBinary(mid+1,Right);
merge(a+Left,a+mid+1,a+mid+1,a+Right+1,tmp);
int tot=0;
for(int i=Left; i<=Right; i++)a[i]=tmp[tot++];
}
int b[maxn],c[maxn];
void Discretization(int* a) {
memcpy(b,a,sizeof(b));
sort(a+1,a+n+1);
int cnt=unique(a+1,a+n+1)-a-1;
for(int i=1; i<=n; i++)b[i]=lower_bound(a+1,a+cnt+1,b[i])-a;
}
int main() {
n=Get_Int();
for(int i=1; i<=n; i++) {
a[i].x=Get_Int();
a[i].y=Get_Int();
a[i].z=Get_Int();
a[i].pos=i;
f[i]=g[i]=1;
c[i]=a[i].z;
}
Discretization(c);
for(int i=1; i<=n; i++)a[i].z=b[i];
sort(a+1,a+n+1,cmp);
for(int i=1; i<=n; i++)a[i].y=i;
sort(a+1,a+n+1);
CDQBinary(1,n);
for(int i=1; i<=n; i++) {
if(f[i]>ans1) {
ans1=f[i];
ans2=g[i];
} else if(f[i]==ans1)ans2=(ans2+g[i])%mod;
}
printf("%d %d\n",ans1,ans2);
return 0;
}

姥爷们赏瓶冰阔落吧~