$cdq$分治浅谈

1.分治思想

  分治实际上是一种思想,这种思想就是将一个大问题划分成为一些小问题,并且这些小问题与这个大问题在某中意义上是等价的。

2.普通分治与$cdq$分治的区别

  普通分治与$cdq$分治都是基于分治思想之上的算法,但是他们是有区别的。普通分治的适用条件是,产生的小问题之间互不影响,然而$cdq$分治就相对比较宽泛,小问题之间可以有影响,但是$cdq$分治不支持强制在线。

3.$cdq$分治浅谈

  分治一共分为四步:

    1) 将当前处理区间分为左右两个等大的子区间;

    2) 递归处理左子区间;

    3) 处理左区间对于右区间的影响,并对于右区间或者答案进行更改与修正;

    4) 递归处理右子区间;

  上面就是$cdq$分治的四个步骤,这四个步骤之中第一、二、四步对于不同的题目来说基本上是相同的,因为毕竟分区间,递归没有什么好更改的。对于不同的题目来说不同点就是第三部,这一步也是$cdq$分治的难点,对于这一步的讲解也要借助于例题。

4.例题

  1) 动态逆序对

  题目描述:对于序列$A$,它的逆序对数定义为满足$i<j$,且$A_i>A_j$的数对$(i,j)$的个数。给1到n的一个排列,按照某种顺序依次删除m个元素,你的任务是在每次删除一个元素之前统计整个序列的逆序对数。

  输入格式:输入第一行包含两个整数$nm$和$mn$,即初始元素的个数和删除的元素个数。以下$n$行每行包含一个$1$到$n$之间的正整数,即初始排列。以下$m$行每行一个正整数,依次为每次删除的元素。$N\le100000 ,M\le50000。$

  输出格式:输出包含$m$行,依次为删除每个元素之前,逆序对的个数。

  思路:首先我们对于这个问题可以转化为二维数点问题,我们将每一个数字的编号作为横坐标,数字本身作为纵坐标标记在平面直角坐标系里,这样我们就可以将每一个点所包含的逆序对数转化为数点问题。例如:3 4 2 1 5,这个序列被转化为图形之后就是下图的样子:

  cdq分治浅谈-LMLPHP

  我们发现上面的有一个规律,对于第三个位置上的二,共参与了三个逆序对。分别为第一个数字,第二个数字和第四个数字。这三个数字对于第三个数字来说都有一个共同的性质,他们都在三号点的左上方和右下方,由于本题是$n$的全排列,且所有数字的编号都不能超过$n$,所以对于当前状态下的数列中的$i$号点来说他参与的逆序对总数,就是由$(0,A_i)$和$(i,n)$围成的矩形中的点数加上由$(i,0)$和$(n,A_i)$围成的矩形中的点数。这样我们就能统计出来每一个点当前参与的逆序对数,对于当前删点后的答案,就是上一个状态减去当前点所参与的逆序对数。

  对于删除操作来说,我们只需要进行赋值就可以了。开始的时候我们将所有的点都赋值成为1,删除的时候就是将当前的赋值成为0。这样矩形内数点就是矩形内统计权值和,这样我们就完成了问题的转化。显然转化成为的问题可以运用$KDtree$来完成,下面讲解一下$cdq$做法。

  对于对点赋值,我们可以转化为对点加值,及加上$\Delta$。我们定义两种操作,$oper=1$的操作中有三个值$x,y,z$,表示将位置为$(x,y)$的点的权值加上$z$。$oper=2$的操作中有四个值$x,y,z,id$,表示统计由$(0,0)$和$(x,y)$围成的矩形中的权值和,并将这个权值和乘上系数$z$加到编号为$id$的答案数组上。对于每一个操作我们都加上一个参数$ord$,表示这个操作的添加顺序。(注:对于每一个矩形的询问操作,我们都能转化为$oper=2$的加减,运用容斥,即可。)

  我们将这些操作进行排序,第一关键字是$x$,第二关键字是$y$。然后就是$solve$。因为更改操作会影响到查询操作,所以$ord$小的点会影响到$ord$大的点,这样的话我们的分治区间就是操作的$ord$编号。我们将$ord$小的点放在左面,$ord$大的放在右面,并且我们不要更改在$solve$之前排序后的相对位置,这样我们的左右区间内依旧保证最开始的相对顺序。

  我们在分划之后就可以递归了,我们先递归左区间,在递归完成之后我们就要处理左区间对于右区间的影响,影响主要在于左区间的修改和右区间的查询。因为我们的左右区间在划分之前是按照最开始的关键字进行的排序,并且最开始的排序方式我们可以用树状数组进行统计答案,但是后来划分的顺序不能,所以本题的步骤顺序有所改变,即先统计左区间对于右区间的影响,后进行左右两个区间的递归处理。

  下面是代码:可以结合代码和上面的描述进行理解。

#include <cstdio>
#include <algorithm>
using namespace std;
#define N 100010
int n,m,idx,place[N],tmp[N];long long ans[N];
struct Oper {int kind,x,y,z,ord,id;}oper[N<<3],tmpx[N<<3];
bool cmp(const Oper &a,const Oper &b)
{return (a.x==b.x&&a.y==b.y)?(a.ord<b.ord):((a.x==b.x)?(a.y<b.y):(a.x<b.x));}
void add(int x,int y) {while(x<=n) tmp[x]+=y,x+=x&-x;}
int find(int x) {int tmp1=0;while(x) tmp1+=tmp[x],x-=x&-x;return tmp1;}
void solve(int l,int r)
{
    if(l==r) return;
    int mid=(l+r)>>1,tl=l-1,tr=mid;
    for(int i=l;i<=r;i++)
    {
		if(oper[i].ord<=mid&&oper[i].kind==1) add(oper[i].y,oper[i].z);
		if(oper[i].ord>mid&&oper[i].kind==2) ans[oper[i].id]+=find(oper[i].y)*oper[i].z;
    }
    for(int i=l;i<=r;i++)
		if(oper[i].ord<=mid&&oper[i].kind==1) add(oper[i].y,-oper[i].z);
    for(int i=l;i<=r;i++)
    {
		if(oper[i].ord<=mid) tmpx[++tl]=oper[i];
		else tmpx[++tr]=oper[i];
    }
    for(int i=l;i<=r;i++) oper[i]=tmpx[i];
    solve(l,mid),solve(mid+1,r);
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1,a;i<=n;i++)
    {
		scanf("%d",&a),oper[++idx].kind=1,oper[idx].x=i;
		oper[idx].y=a,oper[idx].z=1,oper[idx].ord=idx,place[a]=i;
		add(a,1),ans[1]+=i-find(a);
    }
    for(int i=1;i<=n;i++) add(i,-1);
    for(int i=1,a;scanf("%d",&a),i<=m;i++)
    {
		oper[++idx].kind=2,oper[idx].x=place[a],oper[idx].y=n;
		oper[idx].z=-1,oper[idx].ord=idx,oper[idx].id=i+1;
		oper[++idx].kind=2,oper[idx].x=n,oper[idx].y=a;
		oper[idx].z=-1,oper[idx].ord=idx,oper[idx].id=i+1;
		oper[++idx].kind=2,oper[idx].x=place[a],oper[idx].y=a;
		oper[idx].z=2,oper[idx].ord=idx,oper[idx].id=i+1;
		oper[++idx].kind=1,oper[idx].x=place[a],oper[idx].y=a,oper[idx].z=-1,oper[idx].ord=idx;
    }sort(oper+1,oper+idx+1,cmp),solve(1,idx);
    for(int i=2;i<=m;i++) ans[i]+=ans[i-1];
    for(int i=1;i<=m;i++) printf("%lld\n",ans[i]);
}

  2) 陌上花开

  题目描述:有n朵花,每朵花有三个属性:花形$(s)$、颜色$(c)$、气味$(m)$,用三个整数表示。现在要对每朵花评级,一朵花的级别是它拥有的美丽能超过的花的数量。定义一朵花A比另一朵花B要美丽,当且仅当$S_a\ge S_b$,$C_a\ge C_b$,$M_a\ge M_b$。显然,两朵花可能有同样的属性。现在需要统计出评出每个等级的花的数量。

  输入格式:第一行为$N,K (1 \le N \le 100,000, 1 \le K \le 200,000 )$, 分别表示花的数量和最大属性值。以下$N$行,每行三个整数$s_i, c_i, m_i (1 \le s_i, c_i, m_i \le K)$,表示第$i$朵花的属性。

  输出格式:包含$N$行,分别表示评级为$ 0 … N-1 $的每级花的数量。

  思路:首先这道题就是三维偏序的题,我们考虑将每一朵花的三个属性作为三维坐标的第一位,第二维,第三维。例如:1朵花属性分别为:$(3,3,3)$就可以变成下面的样子。

 cdq分治浅谈-LMLPHP

  显然满足花$A$比花$B$美丽的条件是在转化完图形之后点$B$要在点$A$和原点围成的三维图形里面。这个问题显然能用$KDtree$来解决。下面来讲解cdq的做法。

  因为这些花之间只有这三个性质来要求,所以我们就没有必要来按照读入顺序来处理。我们将第一个属性作为第一关键字,第二个属性作为第二个关键字,第三个属性作为第三个关键字进行排序。排序之后相同的花就在一起了,这时我们进行去重,由于我们按照第一关键字已经排序了,所以是不是就转化成为上面那道题的思路了?只是查询没有那么毒瘤而已。

  上面两到例题都是数点问题,同样的类型题还有:bzoj1935[Shoi2007]Tree园丁的烦恼、bzoj2683简单题、bzoj1176[Balkan2007]Mokia。

#include <cstdio>
#include <algorithm>
using namespace std;
#define N 100010
int n,m,tmp[N<<1],ans[N];
struct Flower {int x,y,z,man,hav,id;}flower[N];
bool cmp(const Flower &a,const Flower &b)
{return (a.x!=b.x)?(a.x<b.x):((a.y!=b.y)?a.y<b.y:a.z<b.z);}
bool cmp2(const Flower &a,const Flower &b)
{return (a.y!=b.y)?(a.y<b.y):((a.z!=b.z)?a.z<b.z:a.x<b.x);}
void add(int x,int y) {while(x<=m) tmp[x]+=y,x+=x&-x;}
int find(int x) {int tmp1=0;while(x) tmp1+=tmp[x],x-=x&-x;return tmp1;}
void solve(int l,int r)
{
    if(l==r) return;
    int mid=(l+r)>>1;
    solve(l,mid),solve(mid+1,r),sort(flower+l,flower+r+1,cmp2);
    for(int i=l;i<=r;i++)
    {
		if(flower[i].id<=mid) add(flower[i].z,flower[i].hav);
		else flower[i].man+=find(flower[i].z);
    }
    for(int i=l;i<=r;i++)
		if(flower[i].id<=mid) add(flower[i].z,-flower[i].hav);
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d%d%d",&flower[i].x,&flower[i].y,&flower[i].z);
    sort(flower+1,flower+n+1,cmp);int cnt=0;
    for(int i=1;i<=n;flower[cnt].hav++,i++)
		if(flower[i].x!=flower[i-1].x||flower[i].y!=flower[i-1].y||flower[i].z!=flower[i-1].z)
		    flower[++cnt]=flower[i],flower[cnt].id=cnt,flower[i].hav=flower[i].man=0;
    solve(1,cnt);
    for(int i=1;i<=cnt;i++) ans[flower[i].man+flower[i].hav-1]+=flower[i].hav;
    for(int i=0;i<=n-1;i++) printf("%d\n",ans[i]);
}

  3) [NOI2007]货币兑换Cash

  思路:首先,我们能想到这道题是一道$dp$题目,我们设$f[i]$表示第$i$天能得到的最大收益,这个最大收益也包括第$i$天不进行操作的情况下的收益,设$X[i]$表示第$i$天将所有的现金都兑换成为金券后能拿到的$A$券数,$Y[i]$同理。这是我们发现一个转移式子:$f[i]=Max\{f[i-1],A[i]\times X[j]+B[i]\times Y[j]\}\ (1\le j \le i-1)$。我们发现这个式子能写成斜率优化的样子:$Y[j]=-\frac{A[i]}{B[i]}\times X[j]+\frac{f[i]}{B[i]}$。我们考虑一下能否运用斜率优化,好像可以,对于每一个点的斜率$k$为$-\frac{A[i]}{B[i]}$,横坐标为$X[i]$,纵坐标为$Y[i]$。但是就是有两个不太好的情况,就是每一点的$x$坐标与斜率$k$都不单调,这个怎么办?显然用平衡树维护凸包就好了。我们考虑一下不用平衡树能否实现,我们考虑$cdq$。

  因为正常的要求最大值的斜率优化都是横坐标单调递增,斜率单调递减,所以我们考虑排序。因为每一个点的斜率都是不变的,即输入之后就是定下来的,所以我们可以将这些所有的点都按照斜率递减排序,但是这样就不是按照天数递增的顺序了,所以我们就不能直接运用排序后的顺序来处理这些点。我们将天数进行分治,这样的话我们每一个点就需要再存一个参数,即天数的编号。

  因为这是$dp$,所以我们在递归左区间之后显然要先处理影响,再递归右区间。现在考虑怎么处理影响。

  因为我们每一次处理影响之前都已经处理好左区间了,所以我们现在可以不用理会左区间的具体顺序了,这样的话我们就能对其进行任意顺序的处理,我们可以将左区间的这些点按照横坐标排序,这样我们就能够达到上面所提出的目的,也就是把点按照顺序插入到凸包里面。因为我们是用左区间来更新右区间,所以我们不用去管右区间,并且因为右区间的斜率是单调递减的,所以我们可以按照右区间原本的顺序来进行更新。

  我们在递归出口的地方不能就是直接$return$,我们需要做一些小小的处理,因为我们在$return $之前这个点一定已经做完前面的点的所有更新了,但是没有进行不作处理的更新,所以$f[i]=Max\{f[i],f[i-1]\}$。至此搜有的更新都完成了,这是就可以了处理当前点的横纵坐标。因为必然存在一种最优的买卖方案满足:每次买进操作使用完所有的人民币;每次卖出操作卖出所有的金券,所以当前点的横纵坐标就是$X[i]=\frac{f[i]}{A[i]*Rate[i]+B[i]}\times A[i]$,$Y[i]=\frac{f[i]}{A[i]*Rate[i]+B[i]}$。

  对于横坐标排序,我们显然没有必要每一次都用$sort$,我们运用归并排序的思想,直接排序即可,时间复杂度会降下$O(log_n)$。

#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
#define N 100010
#define eps 1e-9
int n,que[N];double f[N];
struct Node {double a,b,rate,k,x,y;int id;}node[N],tmp[N];
bool cmp(const Node &a,const Node &b) {return a.k>b.k;}
double re_x(int i) {return node[i].x;}
double re_y(int i) {return node[i].y;}
double re_k(int i,int j)
{
    if(fabs(node[i].x-node[j].x)<eps)return 1e20;
    return (re_y(j)-re_y(i))/(re_x(j)-re_x(i));
}
void solve(int l,int r)
{
    if(l==r)
    {
		f[l]=max(f[l],f[l-1]);
		node[l].y=f[l]/(node[l].a*node[l].rate+node[l].b);
		node[l].x=node[l].y*node[l].rate;return;
    }
    int mid=(l+r)>>1,tl=l-1,tr=mid;
    for(int i=l;i<=r;i++) (node[i].id<=mid)?tmp[++tl]=node[i]:tmp[++tr]=node[i];
    for(int i=l;i<=r;i++) node[i]=tmp[i];solve(l,mid);
    int L=1,R=0;
    for(int i=l;i<=mid;i++)
		{while(R>1&&re_k(que[R],que[R-1])<re_k(que[R],i)+eps) R--;que[++R]=i;}
    for(int i=mid+1;i<=r;i++)
    {
		while(L<R&&re_k(que[L],que[L+1])+eps>node[i].k) L++;
		f[node[i].id]=max(f[node[i].id],node[que[L]].x*node[i].a+node[que[L]].y*node[i].b);
    }solve(mid+1,r),tl=l,tr=mid+1;
    for(int i=l;i<=r;i++)
    {
		if((node[tl].x<node[tr].x||tr>r||fabs(node[tl].x-node[tr].x)<eps)&&tl<=mid)
         	tmp[i]=node[tl++];
		else tmp[i]=node[tr++];
    }
    for(int i=l;i<=r;i++) node[i]=tmp[i];
}
int main()
{
    scanf("%d%lf",&n,&f[0]);
    for(int i=1;i<=n;i++)
    {
		scanf("%lf%lf%lf",&node[i].a,&node[i].b,&node[i].rate);
		node[i].k=-node[i].a/node[i].b,node[i].id=i;
    }sort(node+1,node+n+1,cmp),solve(1,n),printf("%.3lf\n",f[n]);
}
01-11 05:02