CDQ分治学习笔记

前言
CDQ分治思想
例题
- 1、翻转对
  - 分析
  - code
P3810 三维偏序（陌上花开）
- 分析
- code

前言

\(CDQ\ 显然是一个人的名字，陈丹琪（NOI2008金牌女选手）。

CDQ分治思想

~~显然CDQ分治不是普通的分治~~
因为这一类问题又有一个共同特点就是 左区间会对右区间产生贡献 。
我们一般要先求左区间的答案，然后再求左区间对右区间的贡献，最后求右区间的答案。
前置知识：归并排序求逆序对，不会的可以看一下这个。
树状数组 也要用到一点。

例题

1、翻转对

题目传送门
题⽬描述
给定⼀个⻓度为 \(n\ 的数组 \(nums\ ,如果 \(i < j\ 且 \(nums[i] > 2 * nums[j]\, 我们就将 \((i , j\ , 称作⼀个重要翻转对。你需要返回给定数组中的重要翻转对的数量。
数据规模
\(n ≤ 100000\

分析

很明显这还只是普通的分治
这题用一个简单的归并排序就可以完成，思路差不多，在归并排序求逆序对的代码稍微改一下，把逆序对变成了翻转对⽽已。

code

很明显这是网上抄的，主要是我的力扣账号忘记密码了

class Solution{
      private int cnt;
      public int reversePairs(int[] nums{
        int len=nums.length;
        sort(nums, Arrays.copyOf(nums, len,0,len-1;
        return cnt;
    }
    private void sort(int[] src,int[] dest,int s,int e{
        if (s>=e{
            return;
        }
        int mid=(s+e>>1;
        sort(dest,src,s,mid;
        sort(dest,src,mid+1,e;
        merge(src,dest,s,mid,e;
    }
    private void merge(int[] src,int[] dest,int s,int mid,int e {
        int i=s,j=mid+1,k=s;
        while (i<=mid&&j<=e{
            if((longsrc[i]>2*((longsrc[j]{
                cnt+=mid-i+1;
                j++;
            } 
            else{
                i++;
            }
        }
        i=s;
        j=mid+1;
        while(i<=mid&&j<=e{
            if (src[i]<=src[j]{
                dest[k++]=src[i++];
            } 
            else{
                dest[k++]=src[j++];
            }
        }
        while(i<=mid{
            dest[k++]=src[i++];
        }
        while(j<=e{
            dest[k++]=src[j++];
        }
    }
}

P3810 三维偏序（陌上花开）

题目传送门
这道题应该是学过 \(CDQ\ 分治的人都做过了（~~毕竟是版题，还是紫色的~~）。
有 $ 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 \ne i $ 的 \(j\ 的数量。

输入格式

第一行两个整数 $ n,k $，表示元素数量和最大属性值。

输出格式

$ n $ 行，第 $ d + 1 $ 行表示 $ f(i = d $ 的 $ i $ 的数量。

样例 #1

样例输入 #1

样例输出 #1

提示

$ 1 \leq n \leq 10^5$，$1 \leq a_i, b_i, c_i \le k \leq 2 \times 10^5 $。

分析

我们把 \(a\ 为第一关键字排序，然后用树状数组动态维护维护 \(b_j \leq b_i\ 的个数，时间复杂度：\(O(n\log_2 n\

我们还是将 \(a\ 数组为第一关键字，\(b\ 数组为第二关键字，\(c\ 数组为第三关键字排序。
然后用类似于普通分治的方法，将 \([l , r]\ 分成 \([l , mid]\ \([mid + 1 , r]\ 两个区间。两个区间内部按照 \(b\ 数组为第一关键字，\(c\ 数组为第二关键字排序，然后同时遍历两个子区间，利⽤树状数组将左区间对右区间的贡献统计到右区间上。
可能有点难懂，大家可以看一下代码感性理解一下，还是比较简单的。

code

#include <bits/stdc++.h>
#define fu(x , y , z for(int x = y ; x <= z ; x ++
#define LL long long
#define fd(x , y , z for(int x = y ; x >= z ; x --
using namespace std;
const int N = 2e5 + 5;
int n , k , tr[N] , ans[N] , m;
struct note {
    int cnt , a , b , c , ans;
}s1[N] , s2[N];
int read ( {
    int val = 0 , fu = 1;
    char ch = getchar (;
    while (ch < '0' || ch > '9' {
        if (ch == '-' fu = -1;
        ch = getchar (; 
    }
    while (ch >= '0' && ch <= '9' {
        val = val * 10 + (ch - '0';
        ch = getchar (;
    }
    return val * fu;
}
bool comp1 (note x , note y {
    if (x.a != y.a return x.a < y.a;
    if (x.b != y.b return x.b < y.b;
    if (x.c != y.c return x.c < y.c;
}
int lowbit (int x { return x & (-x; }
bool comp2 (note x , note y {
    if (x.b != y.b return x.b < y.b;
    return x.c < y.c; 
}
void Insert (int val , int sum {
    int i = val;
    while (i <= k {
        tr[i] += sum;
        i += lowbit(i;
    }
}
int query (int x {
    int sum = 0;
    while (x {
        sum += tr[x];
        x -= lowbit (x;
    }
    return sum;
}
void cdq (int l , int r {
    if (l == r return;
    int mid = l + r >> 1;
    cdq (l , mid , cdq (mid + 1 , r;
    sort (s2 + l , s2 + mid + 1 , comp2;
    sort (s2 + mid + 1 , s2 + r + 1 , comp2;
    int j = l;
    fu (i , mid + 1 , r {
        while (s2[i].b >= s2[j].b && j <= mid {
            Insert (s2[j].c , s2[j].cnt;
            j ++;
        }
        s2[i].ans += query (s2[i].c;
    }
    fu (i , l , j - 1
        Insert (s2[i].c , -s2[i].cnt;
} 
int main ( {
    n = read ( , k = read (;
    fu (i , 1 , n
        s1[i].a = read ( , s1[i].b = read ( , s1[i].c = read (;
    sort (s1 + 1 , s1 + n + 1 , comp1;
    int t = 0;
    s1[n + 1] = {0 , 0 , 0 , 0 , 0};
    fu (i , 1 , n {
        t ++;
        if (s1[i].a != s1[i + 1].a || s1[i].b != s1[i + 1].b || s1[i].c != s1[i + 1].c {
            s2[++ m] = s1[i];
            s2[m].cnt = t;
            t = 0;
        }
    }
    cdq (1 , m;
    fu (i , 1 , m
        ans[s2[i].cnt + s2[i].ans - 1] += s2[i].cnt;
    fu (i , 0 , n - 1 
        printf ("%d\n" , ans[i];
    return 0;
}

编程笔记 » CDQ分治学习笔记

CDQ分治学习笔记