Eternity

Until The End

CDQ分治

发表于 更新于 分类于 ，
本文字数： 9.6k 阅读时长 ≈ 9 分钟

“倒飞的雁，逆流的河，与反方向的时钟。”

偏序问题

一维偏序

求出有多少个 $j(j\neq i)$ ，满足 $j\leq i$ 。

这个太简单了，就直接 std::sort 一波带走，时间复杂度 $\mathcal O(n\log n)$ 。

二维偏序

求出满足 $i\neq j,a_i\leq a_j,b_i\leq b_j$ 的 $j$ 的个数。

我们可以按照 $a_i$ 为第一关键字来排序，然后来查找 $b_i$ 作为条件因子。

如果这里使用枚举 $j:1\sim i$ 暴力的话，时间复杂度高达 $\mathcal O(n^2)$ ，明显不得行。

所以我们选择一个带 $\log$ 的数据结构优化——树状数组。

将 $b$ 离散化，然后每一次查询前缀和（这里的前缀指的是值域），然后加入即可，时间可以优化到 $\mathcal O(n\log n)$ 。

二维偏序同样可以使用分治来做，考虑双关键字排序，即把 $a,b$ 都加入为排序条件。

这样就会出现三种情况：

  • $i,j$ 都在左边；
  • $i,j$ 都在右边；
  • $j$ 在左边，$i$ 在右边。

对于当前指针 $i$ 的左区间 $1\sim i-1$ 肯定满足 $a_k<a_i$ ，那么就和树状数组的做法一样，我们只需要考虑第二维的贡献。

对于前两种情况，可以考虑递归进行处理。

不过，二维偏序问题使用分治做的话可能有些麻烦，大材小用。树状数组应该是当前最合适的算法。

三维偏序

求点 $j(i\neq j)$ 的个数，满足 $a_i\leq a_j,b_i\leq b_j,c_i\leq c_j$ 。

这个问题似乎不可解，但其实做法很多，也很好扩展，也有 $k$ 维偏序问题，就需要算法不断套下去。

而 $\text{CDQ}$ 分治就是一种较为普遍的求解偏序点对问题的思想。

陈丹琦分治

因此得名，而为 $\text{CDQ}$ 分治，这是一个离线算法。

点对问题

所谓点对问题，就是统计一些特性的点对 $(i,j)$ 的数量，即找到点对 $(i,j)$ 满足函数最值。

类似于归并排序，分五步走：

  1. 找到当前序列 $[l,r]$ 的中点 $mid$ ；
  2. 将当前所有点对分为 $3$ 类；
    1. $l\leq i\leq mid,l\leq j\leq mid$ ；
    2. $mid+1\leq i\leq r,mid+1\leq j\leq r$ ；
    3. $l\leq i\leq mid,mid+1\leq j\leq r$ 。
  3. 将当前序列 $[l,r]$ 拆分为 $(l,mid),(mid+1,r)$ ，然后前两种点对会分别在两个序列中。
  4. 递归处理前两种点对。
  5. 设法处理第三种点对。

这样的话，我们把整个序列分为了 $\mathcal O(\log n)$ 层，每一层使用 $\mathcal O(n)$ 的时间来解决，时间复杂度不会高于 $\mathcal O(n\log n)$ ，如果要套上树状数组之类的数据结构的话，时间复杂度就是 $\mathcal O(n\log^2 n)$ 。

经过 $\text{LuckyLeaves}$ 的指导，似乎 $\text{Yxc}$ 的 $\text{CDQ}$ 不太正宗，然后学了一下 $\text{LuckyLeaves}$ 的写法。

  • 首先按照第一关键字排序，并对整个区间进行归并；
  • 然后在当前区间再把小区间按照第二关键字进行排序（不用考虑还原的问题，因为排完小区间之后才会排大区间）；
  • 处理第三关键字；
  • 递归处理。

$\text{Yxc}$ 写的是人工合并，优点是快；$\text{LuckyLeaves}$ 写的是 $\operatorname{Stl}$ 库，优点是好写。

陌上花开

很明显了，三维偏序的板子。

按照 $a$ 维进行排序，然后归并处理 $b,c$ 两维，特判 $b$ 然后用树状数组处理 $c$ 维。

板子大概就长这样，还没贺懂，往后看看。

AC Code 
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
#include<bits/stdc++.h>
#define gh() getchar()
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
    x=0;
    char ch=gh(),t=0;
    while(ch<'0'||ch>'9') t|=ch=='-',ch=gh();
    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=gh();
    if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}
template<class T>
inline void write(T x)
{
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
template<>
inline void write(char c)
{
    putchar(c);
}
template<>
inline void write(char *s)
{
    while(*s) putchar(*s++);
}
template<class T,class ...T1>
inline void write(T x,T1 ...x1)
{
    write(x),write(x1...);
}
template<class T>
inline bool checkMax(T &x,T &y)
{
    return x<y?x=y,1:0;
}
template<class T>
inline bool checkMin(T &x,T &y)
{
    return x>y?x=y,1:0;
}
const int MAXN=1e5+10,MAXM=2e5+10;
int N,M;
struct Node
{
    int a,b,c,s,res;
    bool operator<(const Node &x) const
    {
        if(a!=x.a) return a<x.a;
        if(b!=x.b) return b<x.b;
        return c<x.c;
    }
    bool operator==(const Node &x) const
    {
        return a==x.a&&b==x.b&&c==x.c;
    }
}Q[MAXN],W[MAXN];
int Tre[MAXM],ansd[MAXN];
inline int lowbit(int x)
{
    return x&(-x);
}
inline void add(int x,int v)
{
    for(;x<=M;x+=lowbit(x)) Tre[x]+=v;
}
inline int query(int x)
{
    int res=0;
    for(;x;x-=lowbit(x)) res+=Tre[x];
    return res;
}
void Cdq(int l,int r)
{
    if(l>=r) return ;
    int mid=(l+r)>>1;
    Cdq(l,mid),Cdq(mid+1,r);
    int i=l,j=mid+1,k=0;
    while(i<=mid&&j<=r)
        if(Q[i].b<=Q[j].b) add(Q[i].c,Q[i].s),W[k++]=Q[i++];
        else Q[j].res+=query(Q[j].c),W[k++]=Q[j++];
    while(i<=mid) add(Q[i].c,Q[i].s),W[k++]=Q[i++];
    while(j<=r) Q[j].res+=query(Q[j].c),W[k++]=Q[j++]; 
    for(int i=l;i<=mid;++i) add(Q[i].c,-Q[i].s);
    for(int i=l,j=0;j<k;++i,++j) Q[i]=W[j];
}
int main()
{
    // freopen("cdq-conq.in","r",stdin);
    // freopen("cdq-conq.out","w",stdout);
    read(N,M);
    for(int i=0,a,b,c;i<N;++i)
    {
        read(a,b,c);
        Q[i]=(Node){a,b,c,1};
    }
    std::sort(Q,Q+N);
    int k=1;
    for(int i=1;i<N;++i)
        if(Q[i]==Q[k-1]) ++Q[k-1].s;
        else Q[k++]=Q[i];
    Cdq(0,k-1);
    for(int i=0;i<k;++i)
        ansd[Q[i].res+Q[i].s-1]+=Q[i].s;
    for(int i=0;i<N;++i) write(ansd[i],'\n');
    return 0;
}
/*
10 3
3 3 3
2 3 3
2 3 1
3 1 1
3 1 2
1 3 1
1 1 2
1 2 2
1 3 2
1 2 1
*/

数点问题

老C的任务

如果是 $\mathcal O(n^2)$ 的话，就直接前缀和一遍过了。

意思就是，我们要把原来 $\mathcal O(n^2)-\mathcal O(1)$ 的时间复杂度转换为 $\mathcal O(n\log n)$ 。

考虑把二维数点问题转换维二维偏序问题。

使用矩阵容斥，使问题转化为求四个整区间。然后转换问题：

求满足 $x_i<x,y_i<y$ 的点的个数的权值和。

AC Code 
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
#include<bits/stdc++.h>
#define gh() getchar()
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
    x=0;
    char ch=gh(),t=0;
    while(ch<'0'||ch>'9') t|=ch=='-',ch=gh();
    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=gh();
    if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}
template<class T>
inline void write(T x)
{
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
template<>
inline void write(char c)
{
    putchar(c);
}
template<>
inline void write(char *s)
{
    while(*s) putchar(*s++);
}
template<class T,class ...T1>
inline void write(T x,T1 ...x1)
{
    write(x),write(x1...);
}
template<class T>
inline bool checkMax(T &x,T &y)
{
    return x<y?x=y,1:0;
}
template<class T>
inline bool checkMin(T &x,T &y)
{
    return x>y?x=y,1:0;
}
const int MAXN=5e5+10;
int N,M;
struct Node
{
    int x,y,z,v,id,sign;
    ll sum;
    bool operator<(const Node &t) const
    {
        if(x!=t.x) return x<t.x;
        if(y!=t.y) return y<t.y;
        return z<t.z;
    }
}Q[MAXN],W[MAXN];
ll ans[MAXN];
void Cdq(int l,int r)
{
    if(l>=r) return ;
    int mid=(l+r)>>1;
    Cdq(l,mid),Cdq(mid+1,r);
    int i=l,j=mid+1,k=0;
    ll sum=0;
    while(i<=mid&&j<=r)
        if(Q[i].y<=Q[j].y) sum+=(!Q[i].z)*Q[i].v,W[k++]=Q[i++];
        else Q[j].sum+=sum,W[k++]=Q[j++];
    while(i<=mid) sum+=(!Q[i].z)*Q[i].v,W[k++]=Q[i++];
    while(j<=r) Q[j].sum+=sum,W[k++]=Q[j++];
    for(int i=l,j=0;j<k;++i,++j) Q[i]=W[j];
}
int main()
{
    // freopen("cdq.in","r",stdin);
    // freopen("cdq.out","w",stdout);
    read(N,M);
    for(int i=0,x,y,v;i<N;++i)
    {
        read(x,y,v);
        Q[i]=(Node){x,y,0,v};
    }
    int k=N;
    for(int i=1,xa,xb,ya,yb;i<=M;++i)
    {
        read(xa,ya,xb,yb);
        Q[k++]={xb,yb,1,0,i,1};
        Q[k++]={xa-1,yb,1,0,i,-1};
        Q[k++]={xb,ya-1,1,0,i,-1};
        Q[k++]={xa-1,ya-1,1,0,i,1};
    }
    std::sort(Q,Q+k);
    Cdq(0,k-1);
    for(int i=0;i<k;++i)
        if(Q[i].z) ans[Q[i].id]+=Q[i].sum*Q[i].sign;
    for(int i=1;i<=M;++i) write(ans[i],'\n');
    return 0;
}
/*

*/


AC Code another ver. 
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
#include<bits/stdc++.h>
#define gh() getchar()
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
    x=0;
    char ch=gh(),t=0;
    while(ch<'0'||ch>'9') t|=ch=='-',ch=gh();
    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=gh();
    if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}
template<class T>
inline void write(T x)
{
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
template<>
inline void write(char c)
{
    putchar(c);
}
template<>
inline void write(char *s)
{
    while(*s) putchar(*s++);
}
template<class T,class ...T1>
inline void write(T x,T1 ...x1)
{
    write(x),write(x1...);
}
template<class T>
inline bool checkMax(T &x,T &y)
{
    return x<y?x=y,1:0;
}
template<class T>
inline bool checkMin(T &x,T &y)
{
    return x>y?x=y,1:0;
}
const int MAXN=1e5+10,MAXM=2e5+10;
int N,M,Tre[MAXM],ans[MAXN];
struct Node
{
    int a,b,c,s,res;
}Q[MAXN],D[MAXN];
inline int lowbit(int x)
{
    return x&(-x);
}
inline void add(int x,int v)
{
    for(;x<=M;x+=lowbit(x)) Tre[x]+=v;
}
inline int query(int x)
{
    int res=0;
    for(;x;x-=lowbit(x)) res+=Tre[x];
    return res;
}
inline bool cmpA(Node x,Node y)
{
    if(x.a!=y.a) return x.a<y.a;
    if(x.b!=y.b) return x.b<y.b;
    return x.c<y.c;
}
inline bool cmpB(Node x,Node y)
{
    if(x.b!=y.b) return x.b<y.b;
    return x.c<y.c;
}
void Cdq(int l,int r)
{
    if(l>=r) return ;
    int mid=(l+r)>>1;
    Cdq(l,mid),Cdq(mid+1,r);
    std::sort(D+l,D+mid+1,cmpB);
    std::sort(D+mid+1,D+r+1,cmpB);
    int j=l;
    for(int i=mid+1;i<=r;++i)
    {
        while(D[j].b<=D[i].b&&j<=mid) add(D[j].c,D[j].s),++j;
        D[i].res+=query(D[i].c);
    }
    for(int i=l;i<j;++i) add(D[i].c,-D[i].s);
}
int main()
{
    // freopen("cdq.in","r",stdin);
    // freopen("cdq.out","w",stdout);
    read(N,M);
    for(int i=1;i<=N;++i) read(Q[i].a,Q[i].b,Q[i].c);
    std::sort(Q+1,Q+1+N,cmpA);
    int Tot=0,c=0;
    for(int i=1;i<=N;++i)
    {
        ++c;
        if(Q[i].a!=Q[i+1].a||Q[i].b!=Q[i+1].b||Q[i].c!=Q[i+1].c)
            D[++Tot]=Q[i],D[Tot].s=c,c=0;
    }
    Cdq(1,Tot);
    for(int i=1;i<=Tot;++i) ans[D[i].res+D[i].s-1]+=D[i].s;
    for(int i=0;i<N;++i) write(ans[i],'\n');
    return 0;
}
/*
10 3
3 3 3
2 3 3
2 3 1
3 1 1
3 1 2
1 3 1
1 1 2
1 2 2
1 3 2
1 2 1
*/

逆序对

对于不带修的逆序对的话，直接考虑树状数组怼过去，洛谷难度 $\textcolor{orange}{普及-}$ 。

然后思考带修动态逆序对。

对于第 $i$ 个询问，只有区间 $[1,i-1]$ 内的修改会对此次答案进行影响。同样，在归并的时候，左半段的修改同样会对右半段的询问造成影响。

相关文章