CDQ分治

学习链接

OI Wiki

UntilDawn知乎

BZOJ1935 园丁的烦恼

思路

对于每个查询查分成四个分别进行计数。三维分别为时间、\(x\)、\(y\)，分治时间，归并\(x\)，树状数组\(y\)。

代码

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;

typedef long long LL;
typedef pair pLL;
typedef pair pLi;
typedef pair pil;;
typedef pair pii;
typedef unsigned long long uLL;

#define lson rt<<1
#define rson rt<<1|1
#define lowbit(x) x&(-x)
#define name2str(name) (#name)
#define bug printf("*********\n")
#define debug(x) cout<<#x"=["<> 1;
    CDQ(l, mid); CDQ(mid + 1, r);
    int ls = l;
    for(int rs = mid + 1; rs <= r; ++rs) {
        if(a[rs].op == 2) {
            for( ; ls <= mid && a[ls].x <= a[rs].x; ++ls) {
                if(a[ls].op == 1) add(a[ls].y, a[ls].c);
            }
            ans[a[rs].qid] += a[rs].c * ask(a[rs].y);
        }
    }
    --ls;
    while(ls >= l) {
        if(a[ls].op == 1) add(a[ls].y, -1);
        --ls;
    }
    inplace_merge(a + l, a + mid + 1, a + r + 1, cmp);
}

int main() {
#ifndef ONLINE_JUDGE
    FIN;
#endif
    scanf("%d%d", &n, &q);
    for(int i = 1; i <= n; ++i) {
        scanf("%d%d", &x, &y);
        ++x, ++y;
        a[++tot] = {1, x, y, 1, 0};
    }
    for(int i = 1; i <= q; ++i) {
        scanf("%d%d%d%d", &x, &y, &xx, &yy);
        ++x, ++y, ++xx, ++yy;
        a[++tot] = {2, xx, yy, 1, i};
        a[++tot] = {2, x - 1, yy, -1, i};
        a[++tot] = {2, xx, y - 1, -1, i};
        a[++tot] = {2, x - 1, y - 1, 1, i};
    }
    CDQ(1, tot);
    for(int i = 1; i <= q; ++i) printf("%d\n", ans[i]);
    return 0;
}

BZOJ1176 Mokia

思路

在上面的基础上改成了动态加点，但是处理方式其实是一样的，题目里面的\(s\)是没有用的。

代码

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;

typedef long long LL;
typedef pair pLL;
typedef pair pLi;
typedef pair pil;;
typedef pair pii;
typedef unsigned long long uLL;

#define lson rt<<1
#define rson rt<<1|1
#define lowbit(x) x&(-x)
#define name2str(name) (#name)
#define bug printf("*********\n")
#define debug(x) cout<<#x"=["<> 1;
    cdq(l, mid), cdq(mid + 1, r);
    int ls = l, rs = mid + 1;
    for( ; rs <= r; ++rs) {
        if(a[rs].op == 2) {
            for( ; ls <= mid && a[ls].x <= a[rs].x; ++ls) {
                if(a[ls].op == 1) add(a[ls].y, a[ls].c);
            }
            ans[a[rs].id] += a[rs].c * ask(a[rs].y);
        }
    }
    --ls;
    while(ls >= l) {
        if(a[ls].op == 1) add(a[ls].y, -a[ls].c);
        --ls;
    }
    inplace_merge(a + l, a + mid + 1, a + r + 1);
}

int main() {
#ifndef ONLINE_JUDGE
    FIN;
#endif
    scanf("%*d%d", &w);
    while(1) {
        scanf("%d", &op);
        if(op == 3) break;
        if(op == 1) {
            scanf("%d%d%d", &x, &y, &val);
            a[++tot] = {x, y, 1, val, 0};
        } else {
            scanf("%d%d%d%d", &x, &y, &xx, &yy);
            ++id;
            a[++tot] = {x - 1, y - 1, 2, 1, id};
            a[++tot] = {x - 1, yy, 2, -1, id};
            a[++tot] = {xx, y - 1, 2, -1, id};
            a[++tot] = {xx, yy, 2, 1, id};
        }
    }
    cdq(1, tot);
    for(int i = 1; i <= id; ++i) printf("%d\n", ans[i]);
    return 0;
}

陌上花开

思路

三维偏序，在进行\(cdq\)分治之前需要将相同的进行合并，最后对于相同的花(假设是\(v\))，那么对于\(v\)的等级要加上\(cnt[v]-1\)。三维分别为\(a,b,c\)，分治\(a\)，归并\(b\)，树状数组\(c\)。

代码

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;

typedef long long LL;
typedef pair pLL;
typedef pair pLi;
typedef pair pil;;
typedef pair pii;
typedef unsigned long long uLL;

#define lson rt<<1
#define rson rt<<1|1
#define lowbit(x) x&(-x)
#define name2str(name) (#name)
#define bug printf("*********\n")
#define debug(x) cout<<#x"=["<> 1;
    cdq(l, mid), cdq(mid + 1, r);
    int ls = l, rs = mid + 1;
    while(ls <= mid && rs <= r) {
        if(num[ls].b <= num[rs].b) {
            add(num[ls].c, num[ls].cnt);
            ++ls;
        } else {
            num[rs].ans += ask(num[rs].c);
            ++rs;
        }
    }
    while(rs <= r) {
        num[rs].ans += ask(num[rs].c);
        ++rs;
    }
    --ls;
    while(ls >= l) {
        add(num[ls].c, -num[ls].cnt);
        --ls;
    }
    inplace_merge(num + l, num + mid + 1, num + r + 1, cmp2);
}

int main() {
#ifndef ONLINE_JUDGE
    FIN;
#endif
    scanf("%d%d", &n, &k);
    for(int i = 1; i <= n; ++i) {
        scanf("%d%d%d", &tmp[i].a, &tmp[i].b, &tmp[i].c);
    }
    sort(tmp + 1, tmp + n + 1, cmp1);
    num[++tot] = tmp[1];
    num[tot].cnt = 1;
    num[tot].ans = 0;
    for(int i = 2; i <= n; ++i) {
        if(tmp[i].a == num[tot].a && tmp[i].b == num[tot].b && tmp[i].c == num[tot].c) {
            ++num[tot].cnt, num[tot].ans = 0;
        } else {
            num[++tot] = tmp[i];
            num[tot].cnt = 1;
            num[tot].ans = 0;
        }
    }
    cdq(1, tot);
    for(int i = 1; i <= tot; ++i) {
        ans[num[i].cnt-1+num[i].ans] += num[i].cnt;
    }
    for(int i = 0; i < n; ++i) {
        printf("%d\n", ans[i]);
    }
    return 0;
}

BZOJ3295 动态逆序对

思路

我们先跑出原序列的逆序对，然后用\(cdq\)来计算出删除这个数逆序对的变化值，三维分别为时间、位置、值，分治时间，归并位置，树状数组值。

代码

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;

typedef long long LL;
typedef pair pLL;
typedef pair pLi;
typedef pair pil;;
typedef pair pii;
typedef unsigned long long uLL;

#define lson rt<<1
#define rson rt<<1|1
#define lowbit(x) x&(-x)
#define name2str(name) (#name)
#define bug printf("*********\n")
#define debug(x) cout<<#x"=["<> 1;
    cdq(l, mid), cdq(mid + 1, r);
    int cnt = 0, ls = mid, rs = r;
    for(; rs >= mid + 1; --rs) {
        for(; ls >= l && a[ls].x > a[rs].x; --ls) {
            add(a[ls].tim, 1, m + 1);
            ++cnt;
        }
        if(a[rs].tim != m + 1) ans[a[rs].tim] += cnt - ask(a[rs].tim);
    }
    ++ls;
    while(ls <= mid) {
        add(a[ls].tim, -1, m + 1);
        ++ls;
    }
    cnt = 0, ls = l, rs = mid + 1;
    for(; ls <= mid; ++ls) {
        for(; rs <= r && a[rs].x < a[ls].x; ++rs) {
            add(a[rs].tim, 1, m + 1);
            ++cnt;
        }
        if(a[ls].tim != m + 1) ans[a[ls].tim] += cnt - ask(a[ls].tim);
    }
    --rs;
    while(rs >= mid + 1) {
        add(a[rs].tim, -1, m + 1);
        --rs;
    }
    cnt = ls = l, rs = mid + 1;
    while(ls <= mid && rs <= r) {
        if(a[ls].x < a[rs].x) {
            tmp[cnt++] = a[ls++];
        } else {
            tmp[cnt++] = a[rs++];
        }
    }
    while(ls <= mid) {
        tmp[cnt++] = a[ls++];
    }
    while(rs <= r) {
        tmp[cnt++] = a[rs++];
    }
    for(int i = l; i <= r; ++i) a[i] = tmp[i];
}

int main() {
#ifndef ONLINE_JUDGE
    FIN;
#endif
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; ++i) {
        scanf("%d", &num[i]);
        a[++tot] = {num[i], m + 1};
        vis[num[i]] = tot;
    }
    for(int i = 1; i <= m; ++i) {
        scanf("%d", &x);
        a[vis[x]].tim = i;
    }
    for(int i = 1; i <= n; ++i) {
        sum += i - 1 - ask(num[i]);
        add(num[i], 1, n);
    }
    for(int i = 1; i <= n; ++i) {
        add(num[i], -1, n);
    }
    cdq(1, n);
    for(int i = 1; i <= m; ++i) {
        printf("%lld\n", sum);
        sum -= ans[i];
    }
    return 0;
}

HDU5324 Boring Class

思路

三维分别是位置、\(L\)、\(R\)，分治位置，归并\(R\)，树状数组\(L\)。

由于需要输出字典序最小的方案，因此我们考虑在合并的时候用右边来更新左边的信息，记录每个位置作为\(v_1\)能选出的最大的\(m\)。

代码

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;

typedef long long LL;
typedef pair pLL;
typedef pair pLi;
typedef pair pil;;
typedef pair pii;
typedef unsigned long long uLL;

#define lson rt<<1
#define rson rt<<1|1
#define lowbit(x) x&(-x)
#define name2str(name) (#name)
#define bug printf("*********\n")
#define debug(x) cout<<#x"=["< vec;
int L[maxn], R[maxn], tree[maxn], ans[maxn];

struct node {
    int pos, x, y;
    bool operator < (const node& a) const {
        return y > a.y;
    }
}a[maxn];

void add(int x, int val) {
    while(x <= sz) {
        tree[x] = max(tree[x], val);
        x += lowbit(x);
    }
}

void del(int x) {
    while(x <= sz) {
        tree[x] = 0;
        x += lowbit(x);
    }
}

int ask(int x) {
    int ans = 0;
    while(x) {
        ans = max(ans, tree[x]);
        x -= lowbit(x);
    }
    return ans;
}

bool cmp(node a, node b) {
    return a.pos < b.pos;
}

void cdq(int l, int r) {
    if(l == r) return;
    int mid = (l + r) >> 1;
    cdq(mid + 1, r);
    sort(a + l, a + mid + 1);
    sort(a + mid + 1, a + r + 1);
    int ls = l, rs = mid + 1;
    for(; ls <= mid; ++ls) {
        for(; rs <= r && a[rs].y >= a[ls].y; ++rs) {
            add(a[rs].x, ans[a[rs].pos]);
        }
        ans[a[ls].pos] = max(ans[a[ls].pos], ask(a[ls].x) + 1);
    }
    --rs;
    while(rs >= l) {
        del(a[rs].x);
        --rs;
    }
    sort(a + l, a + mid + 1, cmp);
    cdq(l, mid);
}

int main() {
#ifndef ONLINE_JUDGE
    FIN;
#endif
    while(~scanf("%d", &n)) {
        vec.clear();
        for(int i = 1; i <= n; ++i) scanf("%d", &L[i]), a[i].x = L[i], a[i].pos = i, vec.emplace_back(L[i]);
        for(int i = 1; i <= n; ++i) scanf("%d", &R[i]), a[i].y = R[i], ans[i] = 1;
        sort(vec.begin(), vec.end());
        vec.erase(unique(vec.begin(), vec.end()), vec.end());
        for(int i = 1; i <= n; ++i) a[i].x = lower_bound(vec.begin(), vec.end(), a[i].x) - vec.begin() + 1;
        sz = vec.size();
        cdq(1, n);
        int mx = 0, idx = 1;
        for(int i = 1; i <= n; ++i) {
            if(ans[i] > mx) {
                mx = ans[i];
                idx = i;
            }
        }
        int las = L[idx], lst = R[idx];
        vec.clear();
        vec.emplace_back(idx);
        for(int i = idx + 1; i <= n; ++i) {
            if(ans[i] == mx - 1 && L[i] <= las && R[i] >= lst) {
                mx = ans[i], las = L[i], lst = R[i];
                vec.emplace_back(i);
            }
        }
        printf("%d\n", (int)vec.size());
        for(int i = 0; i < (int)vec.size(); ++i) {
            if(i) printf(" ");
            printf("%d", vec[i]);
        }
        printf("\n");
    }
    return 0;
}

HDU5126 stars

思路

四维偏序，分别为时间，\(x,y,z\)，分治时间和\(x\)，归并\(x,y\)，树状数组\(z\)。

注意第二个\(cdq\)不能改变第一个的数组位置，在第一个\(cdq\)时需要标记每个数组在该分治中是左边一半还是右边一半，如果不标记的话那么在第二次\(cdq\)时就会忽略时间的关系。

代码

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;

typedef long long LL;
typedef pair pLL;
typedef pair pLi;
typedef pair pil;;
typedef pair pii;
typedef unsigned long long uLL;

#define lson rt<<1
#define rson rt<<1|1
#define lowbit(x) x&(-x)
#define name2str(name) (#name)
#define bug printf("*********\n")
#define debug(x) cout<<#x"=["< vec;
int t, q, tot, op, x, y, z, xx, yy, zz, sz;
int tree[maxn], ans[maxn];

struct node {
    int x, y, z, op, id, flag, c;
}a[maxn], tmp[maxn], pp[maxn];

void add(int x, int val) {
    while(x <= sz) {
        tree[x] += val;
        x += lowbit(x);
    }
}

int ask(int x) {
    int ans = 0;
    while(x) {
        ans += tree[x];
        x -= lowbit(x);
    }
    return ans;
}

void cdq2(int l, int r) {
    if(l == r) return;
    int mid = (l + r) >> 1;
    cdq2(l, mid), cdq2(mid + 1, r);
    int ls = l, rs = mid + 1, cnt = l;
    for(; rs <= r; ++rs) {
        for(; ls <= mid && tmp[ls].y <= tmp[rs].y; ++ls) {
            if(tmp[ls].op == 1 && tmp[ls].flag) add(tmp[ls].z, tmp[ls].c);
        }
        if(tmp[rs].op == 2 && !tmp[rs].flag) ans[tmp[rs].id] += tmp[rs].c * ask(tmp[rs].z);
    }
    --ls;
    while(ls >= l) {
        if(tmp[ls].op == 1 && tmp[ls].flag) add(tmp[ls].z, -tmp[ls].c);
        --ls;
    }
    ls = l, rs = mid + 1;
    while(ls <= mid && rs <= r) {
        if(tmp[ls].y < tmp[rs].y) {
            pp[cnt++] = tmp[ls++];
        } else if(tmp[ls].y > tmp[rs].y) {
            pp[cnt++] = tmp[rs++];
        } else if(tmp[ls].z <= tmp[rs].z) {
            pp[cnt++] = tmp[ls++];
        } else {
            pp[cnt++] = tmp[rs++];
        }
    }
    while(ls <= mid) {
        pp[cnt++] = tmp[ls++];
    }
    while(rs <= r) {
        pp[cnt++] = tmp[rs++];
    }
    for(int i = l; i <= r; ++i) tmp[i] = pp[i];
}

void cdq1(int l, int r) {
    if(l == r) return;
    int mid = (l + r) >> 1;
    cdq1(l, mid); cdq1(mid + 1, r);
    int ls = l, rs = mid + 1, cnt = l;
    while(ls <= mid && rs <= r) {
        if(a[ls].x < a[rs].x) {
            tmp[cnt] = a[ls++];
            tmp[cnt++].flag = 1;
        } else if(a[ls].x > a[rs].x) {
            tmp[cnt] = a[rs++];
            tmp[cnt++].flag = 0;
        } else if(a[ls].y < a[rs].y) {
            tmp[cnt] = a[ls++];
            tmp[cnt++].flag = 1;
        } else if(a[ls].y > a[rs].y) {
            tmp[cnt] = a[rs++];
            tmp[cnt++].flag = 0;
        } else if(a[ls].z <= a[rs].z) {
            tmp[cnt] = a[ls++];
            tmp[cnt++].flag = 1;
        } else {
            tmp[cnt] = a[rs++];
            tmp[cnt++].flag = 0;
        }
    }
    while(ls <= mid) {
        tmp[cnt] = a[ls++];
        tmp[cnt++].flag = 1;
    }
    while(rs <= r) {
        tmp[cnt] = a[rs++];
        tmp[cnt++].flag = 0;
    }
    for(int i = l; i <= r; ++i) a[i] = tmp[i];
    cdq2(l, r);
}

int main() {
#ifndef ONLINE_JUDGE
    FIN;
#endif
    scanf("%d", &t);
    while(t--) {
        tot = 0;
        vec.clear();
        scanf("%d", &q);
        int cnt = 0;
        for(int i = 1; i <= q; ++i) {
            scanf("%d%d%d%d", &op, &x, &y, &z);
            if(op == 1) a[++tot] = {x, y, z, op, 0, 0, 1}, vec.push_back(z);
            else {
                scanf("%d%d%d", &xx, &yy, &zz);
                ++cnt;
                a[++tot] = {xx, yy, zz, op, cnt, 0, 1};
                a[++tot] = {x - 1, yy, zz, op, cnt, 0, -1};
                a[++tot] = {xx, y - 1, zz, op, cnt, 0, -1};
                a[++tot] = {xx, yy, z - 1, op, cnt, 0, -1};
                a[++tot] = {x - 1, y - 1, zz, op, cnt, 0, 1};
                a[++tot] = {x - 1, yy, z - 1, op, cnt, 0, 1};
                a[++tot] = {xx, y - 1, z - 1, op, cnt, 0, 1};
                a[++tot] = {x - 1, y - 1, z - 1, op, cnt, 0, -1};
                vec.push_back(z); vec.push_back(z - 1);
                vec.push_back(zz); vec.push_back(zz - 1);
            }
        }
        sort(vec.begin(), vec.end());
        vec.erase(unique(vec.begin(), vec.end()), vec.end());
        sz = vec.size();
        for(int i = 1; i <= tot; ++i) {
            a[i].z = lower_bound(vec.begin(), vec.end(), a[i].z) - vec.begin() + 1;
        }
        cdq1(1, tot);
        for(int i = 1; i <= cnt; ++i) {
            printf("%d\n", ans[i]);
            ans[i] = 0;
        }
    }
    return 0;
}

迷之CDQ