CDQ分治学习笔记

2024-02-24 08:41:10

一直想仔细地研究一下CDQ分治，各种原因导致寄了好久，今天正好有闲兴可以学一下，所以不如按老样子，写一篇学习笔记。

CDQ分治

总述

　　CDQ分治是一个没有固定板子，变化多端的算法，所以很难说它怎么应用到一个确切的地方或者算法，可能在很多地方与DP有关，只是有些情况下状态转移方程不是十分显然的情况，各个子区间对于母区间的转移方式又是清晰的时候，我们可以优先选择CDQ分治来解决问题，还有一个点，CDQ分治比较好写，适合偷懒(不是。

　　同时，CDQ的时间复杂度多在O(n)，可用于解决离线或不强制在线问题中简化一层树结构的实用性分治算法。

　　再提一句，CDQ分治的思想最早由 IOI2008 金牌得主陈丹琦在高中时整理并总结，它也因此得名。

　　在这里，我们将从普通的分治过渡到CDQ分治，分区学习。大体上有三类(比较抽象)：点对有关的问题、1D动态规划的优化和转移、动态转静态(待强化)

浅论分治

　　我们考虑分治的过程不外乎三个步骤：分、解、并。

　　在考虑大规模的问题比较难以解决的时候，可以考虑”多消耗“一些时间与空间，来计算大问题的小问题，再利用小问题的结果来合并求解大问题的答案。同时满足分治有一个前提条件，即是由大问题分解出的子问题其形式应当是与其母问题的形式是相同的，这是保证可以递归处理的条件。

　　解决子问题的方式通常是递归，递归也是优化时间复杂度的有效武器，当把大问题分解成的小问题规模足够小，那么小问题大部分情况是可以常数时间内解决的。

　　将小问题的结果合并来求得大问题的答案。

经典分治的案例

　　归并排序计算逆序数个数。

　　方法很简单，即将对半分成的两个序列各设一个指针 t1,t2 ，再按照大小顺序合成序列。

　　如果a[t1] > a[t2]，那么 t1~mid 的元素一定都比t2大，一定都可以与t2形成逆序对。

　　洛谷P1908逆序对

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<vector>
#define ll long long
#define MAXN 100000005
using namespace std;
int a[MAXN],keep[MAXN],n;
ll ans;
void merge(int s,int t)
{
    if(s == t)
    return;
    int mid = (s + t) >> 1;
    merge(s,mid);
    merge(mid+1,t);
    int i=s,j=mid+1,k=s;
    while(i <= mid && j <= t)
    if(a[i] <= a[j])
    keep[k++] = a[i++];
    else
    {
        keep[k++] = a[j++];
        ans += mid - i + 1;
    }
    while(i <= mid)
    {
        keep[k] = a[i];
        k++;
        i++;
    }
    while(j <= t)
    {
        keep[k] = a[j];
        k++;
        j++;
    }
    for(int i=s;i<=t;i++)
    a[i]=keep[i];
} 
int main()
{
    //merge(1,n);
    //cout << ans;  //求[1,n]中的逆序对数目 
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    scanf("%d",&a[i]);
    merge(1,n);
    printf("%lld",ans);
    return 0;
}

View Code

点对相关问题

　　问题多可以抽象为：给定一个长度为n的序列，统计一些有特性的点对(x,y)的数量/找到一个(x,y)使得一些函数的值最大。

　　算法流程

中点mid
所有点对根据其处的位置分三类(考虑 mid,i,j 三个点的位置关系)
将 1-n 序列划分为 1 -- mid，mid + 1 -- n
对于 i < mid < j 类设法处理

　　整个过程类似于树形结构的处理，需要两种solution，一种是solve(a,b)处理一、三类问题，一种是solve(c,d)处理第二类问题。

三维偏序问题

　　二维偏序问题的处理方式不多赘述，此处从三维偏序问题讲起。(BZOJ 3262 陌上花开)BZOJ停运了没法放链接，居然停运了...

　　题干简述：给定一个序列(a,b)，试求有多少个点对(i,j)满足：i < j && ai < aj && bi < bj

　　思路：先对a排序，消除a的影响，题目就变成了平面上有n个点，按排序后的顺序依次询问有多少点在当前点左下方并插入当前的点。由于只涉及插入与询问操作的离线操作，所以选择cdq分治操作，树状数组维护。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

struct Node
{
    int a,b,c;
    int d,f;
};

Node e[100010],p[100010];

int n,k,tot,ans[100010],cnt,c[200010];

bool cmp(node a,node b)
{
    if (a.a == b.a && a.b == b.b)
    return a.c < b.c;
    if (a.a == b.a)
        return a.b < b.b;
    return a.a < b.a;
}

void add(int x,int v)
{
    while (x <= k)
    {
        c[x] += v;
        x += x & (-x);
    }
    return ;
}

int query(int x)
{
    int res = 0;
    while (x)
    {
        res += c[x];
        x -= x & (-x);
    }
    return res;
}

void solve(int l,int r)
{
    if (l >= r)
        return;
    int mid = (l + r) >> 1;
    solve(l,mid);
    solve(mid + 1,r);
    cnt = l;
    int i = l,j = mid + 1;
    while (i <= mid || j <= r)
    {
        if (j > r || (i <= mid && e[i].b <= e[j].b))
        {
            add(e[i].c,e[i].d);
            p[cnt++] = e[i++];
        }
        else
        {
            e[j].f += query(e[j].c);
            p[cnt++] = e[j++];
        }
    }
    for (int i = l; i <= mid; i++)
        add(e[i].c,-e[i].d);
    for (int i = l; i <= r; i++)
        e[i] = p[i];
}

int main()
{
    scanf("%d%d",&n,&k);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d%d%d",&e[i].a,&e[i].b,&e[i].c);
        e[i].d = 1;
    }
    tot = 1;
    sort(e + 1,e + 1 + n,cmp);
    for (int i = 2; i <= n; i++)
    {
        if (e[i].a == e[tot].a && e[i].b == e[tot].b && e[i].c == e[tot].c)
            e[tot].d++;
        else
            e[++tot] = e[i];
    }
    solve(1,tot);
    for (int i = 1; i <= tot; i++)
        ans[e[i].d + e[i].f - 1] += e[i].d;
    for (int i = 0; i < n; i++)
        printf("%d\n",ans[i]);

    return 0;
}

动态逆序对（非毒瘤）的处理

　　这种地方用CDQ要谨慎，谨防被出题人hack掉。

　　洛谷P3157

　　题目描述：现在给出 1 ∼ n 的一个排列，按照某种顺序依次删除 m 个元素，任务是在每次删除一个元素之前统计整个序列的逆序对数。

　　其实是可以由上一个三维偏序问题差不多的转移。时间复杂度O(n * (logn)^2)

　　关键代码：

struct Node
{
    int a,b,c;
    int n,id;
    friend bool operator < (const Node &op) const
    {
        if(a != op.a)
            return a < op.a;
        if(b != op.a)
            return b < op.a;
        return c < op.c;
    }
};
Node A[MAXN];

bool cmp(const Node &x, const Node &y)
{
    return x.b < y.b;
}

void CDQ(Node A[],int n)
{//a排A 
    if(n == 1)
    {
        ans[A[0].id] += A[0].n - 1;
        return ;
    }
    int mid = n >> 1;
    int k = 0,i = 0,j = mid;
    CDQ(A,mid);
    CDQ(A + mid,n - mid);
    sort(A,A + mid,cmp);
    sort(A + mid,A + n,cmp);
    for(;j < n;j++)
    {
        while(i < mid && A[i].b <= A[j].b)
        {
            update(A[i].c,A[i].n);
            i++;
        }
        ans[A[j].id] += query(A[j].c);
    }
    for(int k=0;k<i;k++)
        update(A[k].c,-A[k].n);
}

View Code

CDQ处理1D动态规划

　　对于一个dp数组，若其为一维数组，那么我们称这个动态规划为1D动态规划。例如最长上升子序列问题，可以从N ^ 2复杂度降低到 N * logN * logN

　　最长上升子序列的状态转移方程：

dp_i = 1 + max_(i=1,j=1)dp_j [a_j < a_i][b_j < b_i]

　　假设现在处理的区间为(l,r)，则函数流程应是：

若 l == r，说明 dp_r 已计算完成，直接dp_r ++
递归solve(l, mid)
处理 l <= j <= mid, mid + 1 <= i <= r 的情况
递归solve(mid + 1, r)

　　处理第三步的时候 j < i 这个条件已经被更强的限制条件限制住了，所以可以不用再考虑他了。因此，我们可以将所有的 i,j 点按a进行排序处理，然后双指针的方式将 j 插入，依然采用树状数组优化，此时只需查最大前缀值更新dp_i。

　　正确性的证明类似于背包问题的压缩空间的思路。CDQ分治是线段树的中序遍历函数，所以说dp是有序的，其前置的条件一定优先于当下的状态而被处理，所以说其正确性成立。

　　这个地方有一个小点：不要用memset，包括点分治在内的分治算法，时间复杂度的正确性关键在于快速处理出小部分的信息，而memset很容易T掉，sizeof函数里面的大小很难清楚把握...

　　洛谷P2487拦截导弹

　　关键代码：

inline void ih(int t)//离散化 
{
      sort(a[t] + 1, a[t] + n + 1, cmp2);
      rk[t][1] = 1;
      for (int i = 2; i <= n; i++)
    {
        rk[t][i] = (cmp4(a[t][i], a[t][i - 1])) ? rk[t][i - 1] : i;
      }
      for (int i = 1; i <= n; i++)
    {
        a[t][i].v = rk[t][i];
      }
      sort(a[t] + 1, a[t] + n + 1, cmp3);
      for (int i = 1; i <= n; i++)
    {
        a[t][i].ma = 1;
        a[t][i].ca = 1;
    }
}

struct treearray//树状数组
{
    int ma[2*N];
    double ca[2*N];
    inline void c(int x,int t,doubleb c)//change
    {
        for(;x<=n;x+=x&(-x))
        {
            if(ma[x] == t)
                ca[x] += c;
            else
            if(ma[x] < t)
            {
                ca[x] = c;
                ma[x] = t;
            }
        }
    }
    inline void d(int x)//delete
    {
        for(;x<=n;x+=x&(-x))
        {
            ma[x] = 0;
            ca[x] = 0;
        }
    }
    inline void q(int x,int& m,double& c)//question , 此cdp非分治的cdq 
    {
        for(;x>0;x-=x&(-x))
        {
            if(ma[x] == m)
                c += ca[x]； 
            else
            if(m < ma[x])
            {
                c = ca[x];
                m = ma[x];
            }
        }
    }
}ta;
int rk[2][N];
inline void solve(int l,int r,int t)//分治 
{
    if(r-l == 1)
    {
        return;
    }
    int mid = (l + r) >> 1;
    solve(l,mid,t);
    sort(a[t] + mid + 1, a[t] + r + 1,cmp1);
    int p = l + 1;
    for(int i=mid+1;i<=r;i++)//维护双指针 ，记得判相等 
    {
        for(;(cmp1(a[t][p],a[t][i]) || a[t][p].h == a[t][i].h) && p <= mid;p++)
            ta.c(a[t][p].v,a[t][p].ma,a[t][p].ca);
        double c = 0;
        int m = 0;
        ta.q(a[t][i].v,m,c);
        if(a[t][i].ma<m+1)
        {
            a[t][i].ma = m + 1;
            a[t][i].ca = c;
        }
        else
        if(a[t][i].ma == m + 1)
            a[t][i].ca += c;
    }
    for(int i=l+1;i<=mid;i++)
        ta.d(a[t][i].v);//记得回撤 
    sort(a[t] + mid,a[t]+r+1,cmp3);
    solve(mid,r,t);//这里sort回来，解决后面 
    sort(a[t] + l + 1,a[t] + r + 1,cmp1);
}

View Code

将动态问题转化为静态问题

　　这种类型常常出现在 ”需要支持做 ... 修改然后做 ... 询问“ 的数据结构题，题目的要求中应当还满足：　　询问离线后，操作将按照时间顺序排列；　　之后的操作与上一步的修改有关，共(N^2)对关系

　　当各个的修改不独立时，在写函数的时候也要记得要用中序遍历来保证按照时间顺序的操作。

　　标准CDQ代码：

inline void solve(int l1, int r1, int l2, int r2, int L, int R)
{  // CDQ
  if (l1 == r1 || l2 == r2) return;
  int mid = (L + R) >> 1;
  int mid1 = l1;
  while (mid1 != r1 && md[mid1 + 1].t <= mid) mid1++;
  int mid2 = l2;
  while (mid2 != r2 && qr[mid2 + 1].t <= mid) mid2++;
  solve(l1, mid1, l2, mid2, L, mid);
  solve(mid1, r1, mid2, r2, mid, R);
  if (l1 != mid1 && mid2 != r2)
  {
    sort(md + l1 + 1, md + mid1 + 1);
    sort(qr + mid2 + 1, qr + r2 + 1);
    for (int i = mid2 + 1, j = l1 + 1; i <= r2; i++)
    {  // 考虑左侧对右侧贡献
      while (j <= mid1 && md[j].pre < qr[i].l)
          ta.c(md[j].pos, md[j].va), j++;
      qr[i].ans += ta.q(qr[i].r) - ta.q(qr[i].l - 1);
    }
    for (int i = l1 + 1; i <= mid1; i++)
        ta.d(md[i].pos);
  }
}

View Code

东风夜放花千树...

　　以上。

码农公寓

CDQ分治

总述

浅论分治

经典分治的案例

点对相关问题

算法流程

三维偏序问题

动态逆序对（非毒瘤）的处理

CDQ处理1D动态规划

将动态问题转化为静态问题

相关文章

　　算法流程