时间分治算法

发表于 | 分类于 | 阅读次数:
对时间的分治算法，又名 CDQ 分治，能用来解决的问题包括但不限于偏序问题，是离线处理繁琐数据结构题的利器，具有代码较短（懒人福利），同复杂度下常数较小的优势。

##[BZOJ3262] 陌上花开

现有 $n$ 朵花，每朵花有三个属性 $a,b,c\leq k$ , 定义花朵 $i$ 比 花朵 $j$ 美丽当且仅当 $a_i\geq a_j,b_i\geq b_j,c_i\geq c_j$ , 一朵花比其它多少朵花美丽它的级别就是多高，统计出每个级别的花朵数量。

$n\leq10^5,k\leq2\times10^5$

这道题就是经典的三维偏序问题，后面比较复杂的题目也大多是要转化到三维偏序问题上来解决的。用时间分治算法解决这种问题的思路就是先按照 $a$ 排序，然后分治到一层按照 $b$ 归并排序，在排序的过程中以 $c$ 为关键字用树状数组统计答案。时间复杂度 $O(n\log_2^2n)$

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
/**************************************************************
    Problem: 3262
    User: zhangche0526
    Language: C++
    Result: Accepted
    Time:1016 ms
    Memory:6372 kb
****************************************************************/
 
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
 
const int MAXN=1e5+5,MAXK=2e5+5;
 
int N,ncnt,K;
 
struct Tri{int a,b,c;int cnt,lv;} flw[MAXN];
bool operator ==(const Tri &x,const Tri &y)
{return x.a==y.a&&x.b==y.b&&x.c==y.c;}
bool operator !=(const Tri &x,const Tri &y){return !(x==y);}
bool operator <(const Tri &x,const Tri &y)
{return x.a<y.a||(x.a==y.a&&x.b<y.b)||(x.a==y.a&&x.b==y.b&&x.c<y.c);}
 
struct FT
{
    int na[MAXK];
    void add(int x,int v){for(;x<=K;x+=x&(-x)) na[x]+=v;}
    int sum(int x){int res=0;for(;x;x-=x&(-x)) res+=na[x];return res;}
    void clean(int x){for(;x<=K;x+=x&(-x)) if(na[x]) na[x]=0;else break;}
} ft;
 
void cdq(int l,int r)
{
    if(l==r) {flw[l].lv=flw[l].cnt-1;return;}
    int i,mid=(l+r)>>1;
    cdq(l,mid);cdq(mid+1,r);
    static Tri tmp[MAXN];
    int p1=l,p2=mid+1;
    for(i=l;i<=r;i++)
    {
        if(p2>r||(p1<=mid&&flw[p1].b<=flw[p2].b))
        {
            tmp[i]=flw[p1++];
            ft.add(tmp[i].c,tmp[i].cnt);
        }
        else
        {
            tmp[i]=flw[p2++];
            tmp[i].lv+=ft.sum(tmp[i].c);
        }
    }
    for(i=l;i<=r;i++) flw[i]=tmp[i],ft.clean(flw[i].c);
}
 
int main()
{
    int i;
    scanf("%d%d",&N,&K);
    for(i=1;i<=N;i++) scanf("%d%d%d",&flw[i].a,&flw[i].b,&flw[i].c),flw[i].cnt=1;
    std::sort(flw+1,flw+1+N);
    for(i=1;i<=N;i++)
        if(flw[i]!=flw[i-1]) flw[++ncnt]=flw[i];
        else flw[ncnt].cnt++;
    cdq(1,ncnt);
    static int ans[MAXN];
    for(i=1;i<=ncnt;i++) ans[flw[i].lv]+=flw[i].cnt;
    for(i=0;i<=N-1;i++) printf("%d\n",ans[i]);
    return 0;
}

[Balkan2007] Mokia

维护一个 $N\times N$ 的矩阵，初始值均为 $S$ . 每次操作可以增加某格子的权值，或询问某子矩阵的总权值。其中，有 $M$ 次修改， $Q$ 次询问

$N\leq2\times10^6,M\leq16\times10^4,Q\leq10^4$

其实上一道题并没有包含时间分治算法的精髓，其最终要的思想其实是每次分治到一个区间 $[l,r]$ 时，将区间划分为 $[l,mid],[mid+1,r]$ 两部分， 对两部分分别按照第二关键字排序，然后考虑左区间中的修改对右区间中的询问的影响。

按照套路，二维子矩阵求和可以利用前缀和快速求出：若 $S(x_1,y_1,x_2,y_2)$ 表示左上角坐标为 $(x_1,y_1)$ , 右下角坐标为 $(x_2,y_2)$ 的子矩阵面积，那么
$$
S(x1,y1,x2,y2)=S(1,1,x2,y2)-S(1,1,x1-1,y2)-S(1,1,x2,y1-1)+S(1,1,x1-1,y1-1)
$$
而求 $S(1,1,x,y)$ 其实就是统计在询问之前且在 $(x,y)$ 左上方的增加权值加上 $xyS$ 的初始权值。这样问题就变成了一个，时间、二维空间的三维偏序问题。

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
/**************************************************************
    Problem: 1176
    User: zhangche0526
    Language: C++
    Result: Accepted
    Time:4092 ms
    Memory:16956 kb
****************************************************************/
 
#include<iostream>
#include<cstdio>
  
const int MAXN=2e6+5,MAXM=16e4+5,MAXQ=1e4+5;
  
int S,N;
  
int ans[MAXQ],acnt;
  
struct Tri
{
    int x,y,ty,v,*ans;
    Tri(){};
    Tri(int x,int y,int ty,int *ans):x(x),y(y),ty(ty),v(0),ans(ans){}
    Tri(int x,int y,int v):x(x),y(y),ty(0),v(v),ans(NULL){}
} opt[MAXM+(MAXQ<<2)];int ocnt;
  
struct FT
{
    int na[MAXN];
    void add(int x,int v){for(;x<=N;x+=x&(-x)) na[x]+=v;}
    int sum(int x){if(!x) return 0;int res=0;for(;x;x-=x&(-x)) res+=na[x];return res;}
    void clean(int x){for(;x<=N;x+=x&(-x)) if(na[x]) na[x]=0;else return;}
} ft;
  
Tri tmp[MAXM+(MAXQ<<2)];
void cdq(int l,int r)
{
    if(l==r) return;
    int i,mid=(l+r)>>1;
    cdq(l,mid);cdq(mid+1,r);
    int p1=l,p2=mid+1;
    for(i=l;i<=r;i++)
    {
        if(p2>r||(p1<=mid&&opt[p1].x<=opt[p2].x))
        {
            tmp[i]=opt[p1++];
            if(!tmp[i].ty) ft.add(tmp[i].y,tmp[i].v);
        }else
        {
            tmp[i]=opt[p2++];
            if(tmp[i].ty) *tmp[i].ans+=ft.sum(tmp[i].y)*tmp[i].ty;
        }
    }
    for(i=l;i<=mid;i++) if(!opt[i].ty) ft.clean(opt[i].y);
    for(i=l;i<=r;i++) opt[i]=tmp[i];
}
  
int main()
{
    int i;
    scanf("%d%d",&S,&N);
    while(true)
    {
        int optTyp;scanf("%d",&optTyp);
        if(optTyp==1)
        {
            int x,y,v;scanf("%d%d%d",&x,&y,&v);
            ocnt++;opt[ocnt]=Tri(x,y,v);
        }else if(optTyp==2)
        {
            int x1,y1,x2,y2;scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
            int *oa=&ans[++acnt];
            *oa=(y2-y1+1)*(x2-x1+1)*S;
            ocnt++;opt[ocnt]=Tri(x2,y2,1,oa);
            ocnt++;opt[ocnt]=Tri(x1-1,y2,-1,oa);
            ocnt++;opt[ocnt]=Tri(x2,y1-1,-1,oa);
            ocnt++;opt[ocnt]=Tri(x1-1,y1-1,1,oa);
        }else break;
    }
    cdq(1,ocnt);
    for(i=1;i<=acnt;i++) printf("%d\n",ans[i]);
    return 0;
}

同样套路的题目：

##[BZOJ2716] 天使玩偶

$n$ 次询问动态平面最近点的曼哈顿距离

$n\leq2\times10^6$

注意到如果只是求左上角的最近点的曼哈顿距离就可以转化成三维偏序问题了，只不过树状数组变成维护最大值而已，而对于原问题在四个方向跑四次分治即可。

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
/**************************************************************
    Problem: 2716
    User: zhangche0526
    Language: C++
    Result: Accepted
    Time:60972 ms
    Memory:38400 kb
****************************************************************/
 
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using std::min;
using std::max;
 
const int MAXN=5e5+5,MAXL=1e6+5;
 
int N,M;
 
struct Tri
{
    int id,x,y,*ans;
    Tri(){}
    Tri(int id,int x,int y,int *ans=NULL):id(id),x(x),y(y),ans(ans){}
} opt[MAXN<<1];int ocnt;
bool cmp(const Tri &a,const Tri &b){return a.id<b.id;}
 
int ans[MAXN],acnt;
 
int mxX,mxY;
 
struct FT
{
    int na[MAXL];
    void umx(int x,int v){for(;x<=mxY;x+=x&(-x)) na[x]=max(na[x],v);}
    int cmx(int x){int res=0;for(;x;x-=x&(-x)) res=max(res,na[x]);return res;}
    void clean(int x){for(;x<=mxY;x+=x&(-x)) if(na[x]) na[x]=0;else return;}
} ft;
 
Tri tmp[MAXN<<1];
void cdq(int l,int r)
{
    if(l==r) return;
    int i,mid=(l+r)>>1;
    cdq(l,mid);cdq(mid+1,r);
     
    int p1=l,p2=mid+1;
    for(i=l;i<=r;i++)
    {
        if(p2>r||(p1<=mid&&opt[p1].x<=opt[p2].x))
        {
            tmp[i]=opt[p1++];
            if(!tmp[i].ans) ft.umx(tmp[i].y,tmp[i].x+tmp[i].y);
        }
        else
        {
            tmp[i]=opt[p2++];
            if(tmp[i].ans)
            {
                int mx=ft.cmx(tmp[i].y);
                if(mx) *tmp[i].ans=min(*tmp[i].ans,tmp[i].x+tmp[i].y-mx);
            }
        }
    }
    for(i=l;i<=mid;i++) if(!opt[i].ans) ft.clean(opt[i].y);
    for(i=l;i<=r;i++) opt[i]=tmp[i];
}
 
int main()
{
    int i;
    scanf("%d%d",&N,&M);
    for(i=1;i<=N;i++)
    {
        int x,y;scanf("%d%d",&x,&y);x++,y++;
        mxX=max(mxX,x),mxY=max(mxY,y);
        ocnt++;opt[ocnt]=Tri(ocnt,x,y);
    }
    for(i=1;i<=M;i++)
    {
        int optTyp;scanf("%d",&optTyp);
        int x,y;scanf("%d%d",&x,&y);x++,y++;
        mxX=max(mxX,x),mxY=max(mxY,y);
        if(optTyp==1) {ocnt++;opt[ocnt]=Tri(ocnt,x,y);}
        else {ocnt++;opt[ocnt]=Tri(ocnt,x,y,&ans[++acnt]);}
    }
    memset(ans,0x3f,sizeof ans);
    cdq(1,ocnt);
    for(i=1;i<=ocnt;i++) opt[i].x=mxX-opt[i].x+1;
    std::sort(opt+1,opt+ocnt+1,cmp);
    cdq(1,ocnt);
    for(i=1;i<=ocnt;i++) opt[i].y=mxY-opt[i].y+1;
    std::sort(opt+1,opt+ocnt+1,cmp);
    cdq(1,ocnt);
    for(i=1;i<=ocnt;i++) opt[i].x=mxX-opt[i].x+1;
    std::sort(opt+1,opt+ocnt+1,cmp);
    cdq(1,ocnt);
    for(i=1;i<=acnt;i++) printf("%d\n",ans[i]);
    return 0;
}

[CQOI2011] 动态逆序对

给定一个 $n$ 个元素的排列，依次删除其中的 $m$ 个元素，求每次删除后的逆序对个数。

$n\leq10^6,m\leq5\times10^5$

正难则反，将原题中的”初始有 $n$ 个元素，依次删除 $m$ 个”改为：“初始有 $n-m$ 个元素，依次加入 $m$ 个”。

之后其实就是一个三维偏序问题了，但不同于一般的三维偏序，本题有两种情况：

  1. 在新加入元素的左边且比新加入元素大的
  2. 在新加入元素的右边且比新加入元素小的

然而我们只能统计出在左边且小的个数，于是我们转换一下统计两次求和即可。

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
/**************************************************************
    Problem: 3295
    User: zhangche0526
    Language: C++
    Result: Accepted
    Time:1492 ms
    Memory:6272 kb
****************************************************************/
 
#include<iostream>
#include<cstdio>
#include<algorithm>
typedef unsigned int uint;
 
const int MAXN=1e5+5,MAXM=5e4+5;
 
int n,m;
 
struct Tri
{
    int id,pos,val;uint *ans;
    Tri(){}
    Tri(int id,int pos,int val,uint *ans):id(id),pos(pos),val(val),ans(ans){}
} opt[MAXN];int ocnt;
bool cmp(const Tri &a,const Tri &b){return a.id<b.id;}
 
struct FT
{
    int na[MAXN];
    void add(int x){for(;x<=n;x+=x&(-x)) na[x]++;}
    int sum(int x){int res=0;for(;x;x-=x&(-x)) res+=na[x];return res;}
    void clean(int x){for(;x<=n;x+=x&(-x)) if(na[x]) na[x]=0;else return;}
} ft;
 
Tri tmp[MAXN];
void cdq(int l,int r)
{
    if(l==r) return;
    int i,mid=(l+r)>>1;
    cdq(l,mid);cdq(mid+1,r);
    int p1=l,p2=mid+1;
    for(i=l;i<=r;i++)
    {
        if(p2>r||(p1<=mid&&opt[p1].pos<=opt[p2].pos))
        {
            tmp[i]=opt[p1++];
            ft.add(tmp[i].val);
        }else
        {
            tmp[i]=opt[p2++];
            *tmp[i].ans+=ft.sum(tmp[i].val);
        }
    }
    for(i=l;i<=mid;i++) ft.clean(opt[i].val);
    for(i=l;i<=r;i++) opt[i]=tmp[i];
}
 
uint ans[MAXN];
int seq[MAXN],pos[MAXN];
int dels[MAXM];bool deld[MAXN];
int main()
{
    int i;
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++) scanf("%d",seq+i),pos[seq[i]]=i;
    for(i=1;i<=m;i++)
    {
        int x;scanf("%d",&x);
        dels[i]=pos[x];
        deld[dels[i]]=true;
    }
    for(i=1;i<=n;i++) if(!deld[i])
    {ocnt++;opt[ocnt]=Tri(ocnt,i,seq[i],&ans[n-ocnt]);}
    for(i=m;i;i--) {ocnt++;opt[ocnt]=Tri(ocnt,dels[i],seq[dels[i]],&ans[i]);}
    for(i=1;i<=n;i++) opt[i].pos=n-opt[i].pos+1;
    cdq(1,n);
    std::sort(opt+1,opt+n+1,cmp);
    for(i=1;i<=n;i++) opt[i].pos=n-opt[i].pos+1,opt[i].val=n-opt[i].val+1;
    cdq(1,n);
    for(i=n;i;i--) ans[i]+=ans[i+1];
    for(i=1;i<=m;i++) printf("%u\n",ans[i]);
    return 0;
}

##[2010 Beijing wc] 纸箱堆叠

有 $n$ 个纸箱，一个纸箱能堆叠在另一纸箱上面当且仅当它的最短边、次短边和最长边长度分别严格小于另一个纸箱的最短边、次短边和最长边长度，从中选择一些纸箱堆叠在一起所能达到的最大纸箱个数n\leq。

$n\leq5\times10^4$

本题就是个裸的三维偏序最长上升子序列。

不过本题还是比较有意义的，因为不同于前面的题目可以直接用时间分治解决，本题分治后还需要进行动态规划，这也就意味着我们之前边归并排序边统计答案的做法不可行了，事实上，前面几道题都是特殊的情况，分治完左右两个区间后再统计答案，而像本题一样的特殊情况下就需要按照先分治左区间、统计答案再分治右区间的一般做法了。

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
/**************************************************************
    Problem: 2253
    User: zhangche0526
    Language: C++
    Result: Accepted
    Time:968 ms
    Memory:4028 kb
****************************************************************/
 
#include<iostream>
#include<cstdio>
#include<algorithm>
using std::min;
using std::max;
typedef long long ll;
const int MAXN=5e4+5;
 
int n;
 
struct Tri
{
    int a,b,c,*f;
    Tri(){}
    Tri(int a,int b,int c,int *f):a(a),b(b),c(c),f(f){}
} itm[MAXN];
bool cmpa(const Tri &x,const Tri &y){return x.a<y.a;}
bool cmpb(const Tri &x,const Tri &y){return x.b<y.b;}
 
int f[MAXN];
 
void mkData(int a,int p)
{
    int i;
    static int ap[MAXN*3];
    for(ap[0]=i=1;i<=3*n;i++) ap[i]=(ll)ap[i-1]*a%p;
    for(i=1;i<=n;i++)
    {
        int tmp[3];
        tmp[0]=ap[i*3-2],tmp[1]=ap[i*3-1],tmp[2]=ap[i*3];
        std::sort(tmp,tmp+3);
        itm[i]=Tri(tmp[0],tmp[1],tmp[2],&f[i]);
    }
}
 
inline void discrt()
{
    int i;
    static int rsp[MAXN];int rcnt;
    for(i=1;i<=n;i++) rsp[i]=itm[i].c;
    std::sort(rsp+1,rsp+n+1);
    rcnt=std::unique(rsp+1,rsp+n+1)-(rsp+1);
    for(i=1;i<=n;i++) itm[i].c=std::lower_bound(rsp+1,rsp+rcnt+1,itm[i].c)-rsp;
}
 
struct FT
{
    int na[MAXN];
    void umx(int x,int v){for(;x<=n;x+=x&(-x)) na[x]=max(na[x],v);}
    int cmx(int x){int res=0;for(;x;x-=x&(-x)) res=max(res,na[x]);return res;}
    void clean(int x){for(;x<=n;x+=x&(-x)) if(na[x]) na[x]=0;else return;}
} ft;
 
int dvd(int l,int r)
{
    int mid=(l+r)>>1;
    while(mid<r&&itm[mid].a==itm[mid+1].a) mid++;
    if(mid<r) return mid;
    mid=(l+r)>>1;
    while(mid>l&&itm[mid].a==itm[mid-1].a) mid--;
    if(mid>l) return mid;
    return 0;
}
 
Tri tmp[MAXN];
void cdq(int l,int r)
{
    if(l==r) return;
    int i,mid=dvd(l,r);
    if(!mid) return;
    cdq(l,mid);
    std::sort(itm+l,itm+mid+1,cmpb);
    std::sort(itm+mid+1,itm+r+1,cmpb);
    int p1=l,p2=mid+1;
    for(i=l;i<=r;i++)
    {
        if(p2>r||(p1<=mid&&itm[p1].b<=itm[p2].b))
        {ft.umx(itm[p1].c,*itm[p1].f+1);p1++;}
        else{*itm[p2].f=max(*itm[p2].f,ft.cmx(itm[p2].c-1));p2++;}
    }
    for(i=l;i<=mid;i++) ft.clean(itm[i].c);
    std::sort(itm+mid+1,itm+r+1,cmpa);
    cdq(mid+1,r);
}
 
int main()
{
    int i;
    int a,p;scanf("%d%d%d",&a,&p,&n);
    mkData(a,p);
    discrt();
    std::sort(itm+1,itm+n+1,cmpa);
    cdq(1,n);
    int ans=0;
    for(i=1;i<=n;i++) ans=max(ans,f[i]+1);
    printf("%d",ans);
    return 0;
}

[BZOJ2961] 共点圆

在平面直角坐标系中，有 $n$ 个操作：

  1. 加入一个以 $(x,y)$ 为圆心且的圆。
  2. 询问点 $(x,y)$ 是否在所有已加入的圆内部（包括边界）且存在已加入的圆。

$n\leq5\times10^5$

其实这道题作为一道分治的题目来说没有什么特殊的地方，放在这里是为了