cdq分治

发表于

这两天半，简单学习了一下cdq分治，先膜一膜cdq。
随便写点东西。

分治算法

分治算法顾名思义，分而治之。
分成若干个子问题，然后得到原问题的解。

cdq分治

理解

有一些问题，可能是修改或者询问。我们不妨把问题分成两部分，先计算好前一半，再计算好后一半，最后再计算前一半修改对后一半询问的影响。
大概思路就这样。

练习

我也就随便做了三个水题。

三维偏序问题

Description

有$ n $个元素，第$ i $个元素有$ a_i $、$ b_i $、$ c_i $三个属性，设$ f(i) $表示满足$ a_j \leq a_i $且$ b_j \leq b_i $且$ c_j \leq c_i $的$ j $的数量。
对于$ d \in [0, n) $，求$ f(i) = d $的数量

Solution

先求$f(i)$。
可以先按$x$排序，这样要求就少一维了。
然后再分治的时候，由于只要分别保证左半边和右半边有序，归并排序掉$y$，用权值BIT维护$z$即可。
注意重复的点。

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
#include <bits/stdc++.h>
using namespace std ;
void Read ( int &x, char c = getchar() ) {
    for ( x = 0 ; !isdigit(c) ; c = getchar() ) ;
    for ( ; isdigit(c) ; c = getchar() ) x = 10*x + c - '0' ;
}
const int maxn = 1e5+5, maxv = 2e5+5 ;
int n, m, k, c[maxv], ans[maxn] ;
int lowbit ( int x ) { return x&(-x) ; }
struct node {
    int x, y, z ;
    int ans, tim ;
} ;
bool cmp1 ( node a, node b ) {
    if (a.x^b.x) return a.x < b.x ;
    if (a.y^b.y) return a.y < b.y ;
    return a.z < b.z ;
}
bool cmp2 ( node a, node b ) { return a.y < b.y ; }
node a[maxn], b[maxn] ;
void add ( int x, int v ) {
    for ( ; x <= m ; x += lowbit(x) ) c[x] += v ;
}
int query ( int x, int v = 0 ) {
    for ( ; x ; x -= lowbit(x) ) v += c[x] ;
    return v ;
}
void solve ( int l, int r ) {
    if (l == r) return ;
    int mid = (l+r)>>1, i, j ;
    solve(l, mid) ;
    solve(mid+1, r) ;
    sort(a+l, a+mid+1, cmp2) ;
    sort(a+mid+1, a+r+1, cmp2) ;
    i = l, j = mid+1 ;
    while (j <= r) {
        while (i <= mid && a[i].y <= a[j].y) {
            add(a[i].z, a[i].tim) ;
            i ++ ;
        }
        a[j].ans += query(a[j].z) ;
        j ++ ;
    }
    for ( -- i ; i >= l ; i -- ) add(a[i].z, -a[i].tim) ;
}
int main() {
#ifndef ONLINE_JUDGE
    freopen ( "P3810.in", "r", stdin ) ;
    freopen ( "P3810.out", "w", stdout ) ;
#endif
    int i ;
    Read(n) ; Read(m) ;
    for ( i = 1 ; i <= n ; i ++ ) {
        Read(b[i].x) ;
        Read(b[i].y) ;
        Read(b[i].z) ;
    }
    sort(b+1, b+n+1, cmp1) ;
    for ( i = 1 ; i <= n ; i ++ )
        if (i == 1 || b[i].x != b[i - 1].x || b[i].y != b[i - 1].y || b[i].z != b[i - 1].z) {
            ++ k ;
            a[k] = b[i] ;
            a[k].tim = 1 ;
        } else ++a[k].tim ;
    solve(1, k) ;
    for ( i = 1 ; i <= n ; i ++ )
        ans[a[i].ans+a[i].tim-1] += a[i].tim ;
    for ( i = 0 ; i < n ; i ++ )
        printf ( "%d\n", ans[i] ) ;
    return 0 ;
}

BZOJ2716天使玩偶

Description

平面坐标系上的一个点集，支持加点，并且询问点集中离某个位置曼哈顿距离的最小值。

Solution

假设询问的点全在给出位置的左下方。
这样只要维护点集$x_i + y_i$的最大值就好了。
轴对称变化，一共做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
#include <bits/stdc++.h>
using namespace std ;
void Read ( int &x, char c = getchar() ) {
    for ( x = 0 ; !isdigit(c) ; c = getchar() ) ;
    for ( ; isdigit(c) ; c = getchar() ) x = 10*x + c - '0' ;
}
const int maxn = 1e6+5, zhf = 0x3f3f3f3f ;
int tot, ans[maxn], n, m, c[maxn], dfn[maxn], modd ;
struct node {
    int x, y, id, op ;
} ;
node a[maxn], s[maxn], t[maxn] ;
void update ( int x, int v ) { for ( ; x <= modd ; x += x&-x ) c[x] = max(c[x], v) ; }
void clear ( int x ) { for ( ; x <= modd ; x += x&-x ) c[x] = 0 ; }
int query ( int x, int v = 0 ) {
    for ( ; x ; x -= x&-x ) v = max(c[x], v) ;
    return v==0? -zhf:v ;
}
void merge ( int l, int r ) {
    int i, mid = (l+r)>>1 ;
    int top1 = l, top2 = mid+1 ;
    for ( i = l ; i <= r ; i ++ )
        if (top2 > r || (top1 <= mid && a[top1].x < a[top2].x)) s[i] = a[top1++] ;
        else s[i] = a[top2++] ;
    for ( i = l ; i <= r ; i ++ ) a[i] = s[i] ;
}
void solve ( int l, int r ) {
    if (l == r) return ;
    int i, j, mid = (l+r)>>1 ;
    solve(l, mid) ;
    solve(mid+1, r) ;
    merge(l, mid) ;
    merge(mid+1, r) ;
    i = l, j = mid+1 ;
    while (j <= r) {
        while (i <= mid && a[i].op == 2) i ++ ;
        while (j <= r && a[j].op == 1) j ++ ;
        if (i <= mid && a[i].x <= a[j].x) {
            update(a[i].y, a[i].x+a[i].y) ;
            i ++ ;
        } else if (j <= r) {
            ans[a[j].id] = min(ans[a[j].id], a[j].x + a[j].y - query(a[j].y)) ;
            j ++ ;
        }
    }
    for ( j = l ; j < i ; j ++ ) clear(a[j].y) ;
}
 
int main() {
#ifndef ONLINE_JUDGE
    freopen ( "BZOJ2716.in", "r", stdin ) ;
    freopen ( "BZOJ2716.out", "w", stdout ) ;
#endif
    int i ;
    Read(n) ; Read(m) ;
    for ( i = 1 ; i <= n+m ; i ++ ) ans[i] = zhf ;
    for ( i = 1 ; i <= n ; i ++ ) {
        Read(t[i].x) ;
        Read(t[i].y) ;
        t[i].x ++ ; t[i].y ++ ;
        t[i].op = 1 ;
        t[i].id = i ;
        modd = max(modd, t[i].y) ;
        modd = max(modd, t[i].x) ;
    }
    for ( i = n+1 ; i <= n+m ; i ++ ) {
        Read(t[i].op) ;
        Read(t[i].x) ;
        Read(t[i].y) ;
        t[i].x ++ ; t[i].y ++ ;
        t[i].id = i ;
        modd = max(modd, t[i].x) ;
        modd = max(modd, t[i].y) ;
        if (t[i].op == 2) dfn[++tot] = i ;
    }
    n += m ;
    modd ++ ;
    for ( i = 1 ; i <= n ; i ++ )
        a[i] = t[i] ;
    solve(1, n) ;
     
    for ( i = 1 ; i <= n ; i ++ ) {
        a[i] = t[i] ;
        a[i].x = modd - a[i].x ;
    }
    solve(1, n) ;
 
    for ( i = 1 ; i <= n ; i ++ ) {
        a[i] = t[i] ;
        a[i].y = modd - a[i].y ;
    }
    solve(1, n) ;
 
    for ( i = 1 ; i <= n ; i ++ ) {
        a[i] = t[i] ;
        a[i].x = modd - a[i].x ;
        a[i].y = modd - a[i].y ;
    }
    solve(1, n) ;
     
    for ( i = 1 ; i <= tot ; i ++ )
        printf ( "%d\n", ans[dfn[i]] ) ;
    return 0 ;
}

CQOI2011动态逆序对

Description

给出$n$的一个排列，在排列中删除一些数，求每次删除前序列的逆序对数量。
这种只有删除的通常都变成增加来做。
注意，增加一个数，会对前面和后面的都有影响，所以需要后面轴对称变化一下再做一次。
通常逆序对问题都是要long long的。

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
#include <bits/stdc++.h>
#define LL long long
using namespace std ;
const int maxn = 1e6+5 ;
int n, m, c[maxn], dfn[maxn] ;
LL ans[maxn] ;
void update ( int x, int v ) {
    for ( ; x <= n ; x += x&-x ) c[x] += v ;
}
int query ( int x, int rec = 0 ) {
    for ( ; x ; x -= x&-x ) rec += c[x] ;
    return rec ;
}
struct node {
    int x, y, id ;
    friend bool operator < ( node a, node b ) {
        return a.x < b.x ;
    }
} a[maxn], b[maxn] ;
void merge ( int l, int r ) {
    if (l == r) return ;
    int i, mid = (l+r)>>1 ;
    int top1 = l, top2 = mid+1 ;
    for ( i = l ; i <= r ; i ++ )
        if (top2 > r || (top1 <= mid && a[top1].id < a[top2].id)) b[i] = a[top1++] ;
        else b[i] = a[top2++] ;
    for ( i = l ; i <= r ; i ++ ) a[i] = b[i] ;
}
void solve ( int l, int r ) {
    if (l == r) return ;
    int i, j, mid = (l+r)>>1 ;
    solve(l, mid) ;
    solve(mid+1, r) ;
    merge(l, mid) ;
    merge(mid+1, r) ;
    for ( i = l, j = mid+1 ; j <= r ; j ++ ) {
        while (i <= mid && a[i].id <= a[j].id) {
            update(a[i].y, 1) ;
            i ++ ;
        }
        ans[a[j].id] += (LL)(query(n) - query(a[j].y)) ;
    }
    for ( j = l ; j < i ; j ++ ) update(a[j].y, -1) ;
}
bool vis[maxn] ;
int main() {
#ifndef ONLINE_JUGDE
    freopen ( "P3157.in", "r", stdin ) ;
    freopen ( "P3157.out", "w", stdout ) ;
#endif
    int i, k ;
    scanf ( "%d%d", &n, &m ) ;
    for ( i = 1 ; i <= n ; i ++ ) {
        scanf ( "%d", &k ) ;
        dfn[k] = i ;
        a[i] = (node){i, k, i} ;
    }
    for ( i = 1 ; i <= m ; i ++ ) {
        scanf ( "%d", &k ) ;
        vis[k] = 1 ;
        a[n+i] = (node){dfn[k], k, n+m-i+1} ;
    }
    sort(a+1, a+n+m+1) ;
    k = 0 ;
    for ( i = 1 ; i <= n+m ; i ++ )
        if (vis[a[i].y] && a[i].id <= n) continue ;
        else b[++k] = a[i] ;
    for ( i = 1 ; i <= n ; i ++ ) a[i] = b[i] ;
    solve(1, n) ;
    for ( i = 1 ; i <= n ; i ++ ) {
        a[i].x = n-a[i].x+1 ;
        a[i].y = n-a[i].y+1 ;
    }
    sort(a+1, a+n+1) ;
    solve(1, n) ;
    memset ( vis, 0, sizeof vis ) ;
    for ( i = 1 ; i <= n ; i ++ )
        vis[a[i].id] = 1 ;
    for ( i = 1 ; i <= n+m ; i ++ )
        ans[i] += ans[i-1] ;
    for ( i = n+m ; i > n ; i -- )
        printf ( "%lld\n", ans[i] ) ;
    return 0 ;
}