离线算法——CDQ分治

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

  • 从归并开始（这里并没有从逆序对开始，是想直接引入分治思想，而不是引入处理对象）

　　一个很简单的归并排序：一个乱序的数列，每次将其折半，类似于线段树这样的数据结构，每个子区间先处理好，最后汇总到上一层。

其中层数不超过log(n)层，每次处理的复杂度是O(n)的，因此其复杂度为O(nlogn)。

　　code：

void merge_sort(int l,int r)

{

    if(l==r)return;

    int mid=(l+r>>);

    merge_sort(l,mid);merge_sort(mid+,r);

    int i=l,j=mid+,k=l;

    while(i<=mid&&j<=r)

    {

        if(a[i]<a[j])t[k++]=a[i++];

        else t[k++]=a[j++];

    }

    while(i<=mid)t[k++]=a[i++];

    while(j<=r)t[k++]=a[j++];

    go(i,l,r)a[i]=t[i];

}

  • 　　简单应用（逆序对）

　　逆序对就是求数列中满足i<j&&a[i]>a[j]的二元组(i,j)的对数。

　　举个栗子（真好吃）：1,4,3,8,4,3,8(val)

　　　　　　　　　　　　1,2,3,4,5,6,7(pos)

　　对于pos：(2,3),(2,6),(4,5),(4,6),(5,6)都是逆序对

　　于是就我们可以由归并的性质：因为pos已经天然有序，因此我们只要看val就可以了。

　　在merge时，如果右边的当前位置j比左边的位置i小，那么它一定比[i,mid]中的所有数都小，因此ans+=mid-i+1。

  • 　　从逆序对到二维偏序问题

　　二维偏序问题其实就是把逆序对的pos打乱，且会重复，它可以理解为在平面直角坐标系中，有n个点(i,j)，求每个点和(0,0)形成的矩形内有多少个点。

　　双关键字排序后直接树状数组即可：

　　例题：二维偏序

#include<iostream>

#include<algorithm>

#include<cstdio>

#include<cstring>

#define lowbit(x) (x&-x)

using namespace std;

const int N=;

struct star

{

    int x,y;

}s[N];

long long tarr[N];

int n;

long long ans;

bool cmp(star a,star b)

{

    return a.x==b.x?a.y<b.y:a.x<b.x;

}

void add(int pos,int val)

{

    while(pos<=N)

    {

        tarr[pos]+=val;

        pos+=lowbit(pos);

    }

}

int query(int pos)

{

    int res=;

    while(pos)

    {

        res+=tarr[pos];

        pos-=lowbit(pos);

    }return res;

}

int main()

{

    scanf("%d",&n);

    for(int i=;i<=n;i++)

    {

        scanf("%d%d",&s[i].x,&s[i].y);

    }

    sort(s+,s++n,cmp);

    for(int i=;i<=n;i++)

    {

        ans+=query(s[i].y);

        add(s[i].y,);

    }

    cout<<ans;

}

  • 　　 从二维偏序到三维偏序

　　板子：陌上花开

　　有了之前的基础，三维偏序也很简单：

　　我们按三关键字排序，(优先级a>b>c)，对第二位进行归并排序，在merge时，对于左边的i和右边的j，如果第二维满足(bi<bj)，则在树状数组中加入ci,直到存在某个bi不满足此关系，则j可以查询树状数组中所有ci<cj的三元组，由于之前对第一维的排序和对第二维的归并，前两维一定是满足条件的。这里有个去重还是挺烦的。

code:

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#define lowbit(x) (x&-x)

using namespace std;

const int N=;

const int M=;

struct node

{

    int a,b,c,f,w;

}e[N],t[N];

int cnt;

int n,m;

int ans[N];

int tarr[M];

bool cmp(node x,node y)

{

    return x.a==y.a?(x.b==y.b?x.c<y.c:x.b<y.b):x.a<y.a;

}

void add(int pos,int val)

{

    while(pos<=m)

    {

        tarr[pos]+=val;

        pos+=lowbit(pos);

    }

}

int query(int pos)

{

    int res=;

    while(pos)

    {

        res+=tarr[pos];

        pos-=lowbit(pos);

    }return res;

}

void CDQ(int l,int r)

{

    if(l==r)return;

    int mid=(l+r>>);

    CDQ(l,mid);CDQ(mid+,r);

    int i=l,j=mid+,k=l;

    while(i<=mid&&j<=r)

    {

        if(e[i].b<=e[j].b)add(e[i].c,e[i].w),t[k++]=e[i++];

        else e[j].f+=query(e[j].c),t[k++]=e[j++];

    }

    while(i<=mid)add(e[i].c,e[i].w),t[k++]=e[i++];

    while(j<=r)e[j].f+=query(e[j].c),t[k++]=e[j++];

    for(int i=l;i<=mid;i++)add(e[i].c,-e[i].w);

    for(int i=l;i<=r;i++)e[i]=t[i];

}

int main()

{

    scanf("%d%d",&n,&m);

    for(int i=;i<=n;i++)

    scanf("%d%d%d",&e[i].a,&e[i].b,&e[i].c),e[i].w=;

    sort(e+,e++n,cmp);

    cnt=;

    for(int i=;i<=n;i++)

    {

        if(e[i].a==e[cnt].a&&e[i].b==e[cnt].b&&e[i].c==e[cnt].c)

        e[cnt].w++;

        else e[++cnt]=e[i];

    }

    CDQ(,cnt);

    for(int i=;i<=cnt;i++)ans[e[i].f+e[i].w-]+=e[i].w;

    for(int i=;i<n;i++)printf("%d\n",ans[i]);

}

  • 　　应用：

　　Mokia

　　这是一个三维偏序问题，我们把时间当做第一维，x当做第二维，y当做第三维。

　　按照处理三维偏序的思路，我们先按(t>x>y)排序，对x进行归并，对y进行树状数组。

　　但是此题的查询比较烦：它查询的是矩阵前缀和。因此对每个查询，我们要处理四个区间的前缀和。这里我把一次询问拆成了四次询问。

　　具体细节看code：

　　

#include<iostream>

#include<algorithm>

#include<cstring>

#include<cstdio>

#define lowbit(x) (x&-x)

using namespace std;

const int W=;

const int Q=;

struct node

{

    int id,x,y,t,sum;//id为时间，t为类型（add还是query），t=0，sum为添加的值，

                     //t=1，sum为返回值

}e[Q],t[Q];

int cnt;

int tarr[W];

inline int read()

{

    int x=,f=;char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

    while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

    return x*f;

}

int w;

bool cmp(node a,node b)

{

    return a.id==b.id?(a.x==b.x?a.y<b.y:a.x<b.x):a.id<b.id;

}

bool cmp2(node a,node b)

{

    return a.id<b.id;

}

void add(int pos,int val)

{

    while(pos<=W)

    {

        tarr[pos]+=val;

        pos+=lowbit(pos);

    }

}

int query(int pos)

{

    int res=;

    while(pos)

    {

        res+=tarr[pos];

        pos-=lowbit(pos);

    }return res;

}

void CDQ(int l,int r)//CDQ分治和归并板子其实没啥本质区别

{

    if(l==r)return;

    int mid=(l+r>>);

    CDQ(l,mid);CDQ(mid+,r);

    int i=l,j=mid+,k=l;//基本操作

    while(i<=mid&&j<=r)

    {

        if(e[i].x<=e[j].x)//对第二维进行归并，如果满足条件，把第三维的贡献放到树状数组里

        {

            if(e[i].t==)add(e[i].y,e[i].sum);//此时t需要为0

            t[k++]=e[i++];

        }

        else

        {

            if(e[j].t==)e[j].sum+=query(e[j].y);//如果已经没有满足条件的x了，我们就进行统计

            t[k++]=e[j++];//此时t需要为1

        }

    }

    while(i<=mid)

    {

        if(e[i].t==)

        add(e[i].y,e[i].sum);

        t[k++]=e[i++];

    }

    while(j<=r)

    {

        if(e[j].t==)

        e[j].sum+=query(e[j].y);

        t[k++]=e[j++];

    }//统计剩下的

    for(int i=l;i<=mid;i++)if(e[i].t==)add(e[i].y,-e[i].sum);//必须要清空树状数组

    for(int i=l;i<=r;i++)

    e[i]=t[i];

}

int main()

{

    while()

    {

        int cid=read();

        if(cid==)w=read();

        if(cid==)

        {

            int x=read()+,y=read()+,z=read();

            e[++cnt]=(node){cnt,x,y,,z}; //结构体直接读取

        }

        if(cid==)

        {

            int i=read(),j=read(),x=read()+,y=read()+;//x，y可能为0，树状数组会爆

            e[++cnt]=(node){cnt,i,j,,};//因此它们都要加一，对结果无影响

            e[++cnt]=(node){cnt,i,y,,};

            e[++cnt]=(node){cnt,x,j,,};

            e[++cnt]=(node){cnt,x,y,,};//一个询问拆成四个询问

        }

        if(cid==)break;

    }

    sort(e+,e++cnt,cmp);//对第一维排序

    CDQ(,cnt);

    sort(e+,e++cnt,cmp2);//查询之前一定要按时间排好序，因为已经按第二维归并了一遍

    for(int i=;i<=cnt;i++)

    {

        int ans=;

        if(e[i].t==)

        {

            int a=e[i].sum,b=e[i+].sum,c=e[i+].sum,d=e[i+].sum;

            ans=a-b-c+d;printf("%d\n",ans);//遇到查询，4个合并起来就是最终答案

            i+=;

        }

    }

}

　　二维偏序很好懂，三维偏序太难画，所以这里就不放图了

　　完美撒花✿✿ヽ(°▽°)ノ✿

　　——Thranduil

最新文章

  1. Java Thread 的使用
  2. 【转载】Arcengine效率探究之二——属性的更新
  3. PullToRefreshListView相关
  4. 设置默认访问项目的客户端的浏览器版本（IE版本）
  5. js字符拼接
  6. No.019：Remove Nth Node From End of List
  7. Careercup - Microsoft面试题 - 5673934611546112
  8. 一个简单的DDraw应用程序2
  9. [Oracle] - 性能优化工具（5） - AWRSQL
  10. c# WPF 项目优化
  11. Annotation(一)——注解开发介绍
  12. Silence.js高效开发移动Web前端类库
  13. VMware安装CentOS 图文教程
  14. poj2398计算几何叉积
  15. Spring Mvc 用Demo去学习
  16. json篇
  17. 4.21Linux(2)
  18. JAVA课程设计-教学论坛系统
  19. 7-unittest和requests重构、封装处理get/post请求
  20. python多线程中锁的概念

热门文章

  1. Java读源码之ThreadLocal
  2. 深入理解C# 委托（delegate）-戈多编程
  3. .netCore+Vue 搭建的简捷开发框架--目录
  4. postman全局变量设置
  5. Webshell免杀绕过waf
  6. [USACO17JAN]Building a Tall Barn建谷仓
  7. opencv::模板匹配(Template Match)
  8. C# 关于config文件中的usersettings
  9. 每日温度（LeetCode Medium难度算法题）题解
  10. Spring Boot2 系列教程(十七)SpringBoot 整合 Swagger2