CDQ分治与总体二分小结

前言

  这是一波强行总括。

  上面是一波瞎反复。

  近来做了几道CDQ/全体二分,感到自身做题速度好慢啊。

  比很多很引人瞩目标东西都看不出来
分治分不出来 打不出来 调不对

  深夜午后晚间的功用完全不等同啊。

  完蛋.jpg 绝望.jpg。

 

关于CDQ分治

  CDQ分治,求的是三维偏序难点都明白的。

  求法呢,正是在分治外面先把一维产生有序

  然后分治下去,左侧(l,mid)关于右侧(mid+1,r)就不设有某一维的逆序了,所以独有两维偏序了。

  那一年来一波”树状数组求逆序对”的操作搞一下二维偏序

  就能够把跨过中线的,左侧更新右侧的意况计算出来。

  在意:只计算左边的操作对左侧的明白的贡献!

  然后左右两侧递归管理就好了。

  准确性:根据线段树的造型递归的CDQ分治,保障每一对伊利组在线段树上都有且独有三个LCA(那不废话吗),而这一组答案就能够且仅会在LCA处计算。假如在LCA上面,点对不在多个work内自然不会总结。即便在LCA上边了,点对就在同一侧,不会互相更新。

  复杂度:设贰遍work的复杂度是f(len),则复杂度是O(f(n)logn)。

  一般都在分治里用树状数组,一般的复杂度正是O(nlog2n)的。

  一般是这么的老路:要是三个维度偏序分别为a,b,c;

  在main函数里保险a递增。

  然后在CDQ里先分治左右,传下去的时候a仍旧递增,不损坏性质。

  然后分治完左右两侧后,需保障左右两侧分别b都以多如牛毛的(a不首要)。

  然后就是近乎归并排序的操作了。

  此时左臂的a显明都自愧不及右侧的a,那么只要对于七个动手的要素

  从前好像归并的操作就足以确认保证具有小于b的左侧的成分都已经遍历过。

  那么找c也低于它的?值域线段树/树状数组等数据结构维护一下就好了。

  然后你这么归并了一波后,就意识总结完答案后b是稳步递增的了(这年a已经不重大了)。

  对于上层操作,符合”左右两侧分别b是多如牛毛的”了。

  BZOJ陌上花开竟然是权力题?那是在好笑。

  好吧BZOJ动态逆序对,在此之前写过的,做一遍CDQ就好了。

  BZOJ稻草人,也是CDQ。

 

还应该有三个便是高维偏序难点。

cogs上的2479 HZOI二〇一五 偏序
就是四维偏序板子。

前面还应该有三个抓好版,到了七维,不是CDQ干的事体,实际情况请见这个PPT

那边只谈谈四维偏序,即a<a’   b<b’  
c<c’   d<d’。

做法是喜人的CDQ套CDQ套树状数组。

有个很妙的博客:Candy?

先是在外头遵照a排好序。

进第一层CDQ。先递归管理,然后标识本来是在mid左侧依旧侧边的,左1右0,然后按b排序。

要么只总计左侧部分跨过中线对左边部分的孝敬。

依据b排好序后,就成为了总括标志为0的点的”在它侧面的、标识为1的、(c,d)都低于它的点的个数”。

“在它侧面+(c,d)都自愧不如它” =
三个维度偏序。

复制到另二个数组里再做一回cdq就可以了。

复杂度O(nlog^3n)。

 

葡京娱乐注册 1葡京娱乐注册 2

#include    <iostream>
#include    <cstdio>
#include    <cstdlib>
#include    <algorithm>
#include    <vector>
#include    <cstring>
#include    <queue>
#include    <complex>
#include    <stack>
#define LL long long int
#define dob double
#define FILE "partial_order"
//#define FILE "CDQ"
using namespace std;

const int N = 100010;
struct Data{int a,b,c,id;}p[N],que[N],que2[N];
int n,vis[N],tim,T[N];
LL Ans;

inline int gi(){
  int x=0,res=1;char ch=getchar();
  while(ch>'9'||ch<'0'){if(ch=='-')res*=-1;ch=getchar();}
  while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
  return x*res;
}

inline void update(int x){
  for(;x<=n;x+=x&-x){
    if(vis[x]!=tim)T[x]=0,vis[x]=tim;
    T[x]++;
  }
}

inline int query(int x,int ans=0){
  for(;x;x-=x&-x){
    if(vis[x]!=tim)T[x]=0,vis[x]=tim;
    ans+=T[x];
  }
  return ans;
}

inline void cdq(int l,int r){
  if(l==r)return;
  int mid=(l+r)>>1,i=l,j=mid+1,k=l;
  cdq(l,mid);cdq(mid+1,r);tim++;
  while(i<=mid && j<=r){
    if(que[i].b<que[j].b){
      if(que[i].id)update(que[i].c);
      que2[k++]=que[i++];
    }
    else{
      if(!que[j].id)Ans+=query(que[j].c);
      que2[k++]=que[j++];
    }
  }
  while(i<=mid)que2[k++]=que[i++];
  while(j<=r){
    if(!que[j].id)Ans+=query(que[j].c);
    que2[k++]=que[j++];
  }
  for(k=l;k<=r;++k)que[k]=que2[k];
}

inline void CDQ(int l,int r){
  if(l==r)return;
  int mid=(l+r)>>1,i=l,j=mid+1,k=l;
  CDQ(l,mid);CDQ(mid+1,r);
  while(i<=mid && j<=r){
    if(p[i].a<p[j].a)que[k]=p[i++],que[k++].id=1;
    else que[k]=p[j++],que[k++].id=0;
  }
  while(i<=mid)que[k]=p[i++],que[k++].id=1;
  while(j<=r)que[k]=p[j++],que[k++].id=0;
  for(k=l;k<=r;++k)p[k]=que[k];cdq(l,r);
}

int main()
{
  freopen(FILE".in","r",stdin);
  freopen(FILE".out","w",stdout);
  n=gi();
  for(int i=1;i<=n;++i)p[i].a=gi();
  for(int i=1;i<=n;++i)p[i].b=gi();
  for(int i=1;i<=n;++i)p[i].c=gi();
  CDQ(1,n);printf("%lld\n",Ans);
  fclose(stdin);fclose(stdout);
  return 0;
}

CDQ套CDQ

 

 

 

 

有关全体二分

  全体二分珍视是把装有询问放在一同二分答案,然后把操作也共同分治。

  哪一天用呢?

  当您发掘多组精通能够离线的时候

  当你发掘询问能够二分答案而且check复杂度对于单组询问能够承受的时候

  当你意识询问的操作都以同一的的时候

  你就足以行使完全二分这么些事物了。

  具体做法讲起来有一点玄学,其实看似主席树转化到距离的操作照旧线段树上二分。

  想想:二分答案的时候,对于二个答案,是还是不是有一些操作是没用的,有些操作进献是不改变的?

  比方二分二个时刻,那么时间前边爆发的操作正是从未用的,时间前边的孝敬是不改变的。

  二分二个最大值,比mid大的都以没用的,比mid小的个数是不容置疑的。

  全体二分正是利用了那样八性格质。

  二分答案,然后把尚未用的操作扫进右侧,和答案在[mid+1,r]的询问一齐递归管理。

  把实用的操作放进左侧,减去不变的进献,和答案在[l,mid]的一块递归管理。

  注意答案在[mid+1,r]的摸底要算上放进了左边的操作的进献,开个变量记下来/间接压缩都得以。

  注意全体二分在solve内的复杂度一定只可以与区间长度线性相关,无法每一次都有其他复杂度!

  比方一遍solve的复杂度是O(lenlogn)就足以,O(len+sqrt(n))就老大。

  大致就是如此贰个事物。

  复杂度?和CDQ是同样的,都以O(f(len)logn)。

  例题?BZOJ3110
K大数查询 Codevs Meteors。

  同样的老路了。

葡京娱乐注册, 

至于部分要留神的地方

  归并肯定要把剩下的搞完!每一遍小编都记不清那码子事!

  树状数组不能够暴力清零!记个time也许依葫芦画瓢减回去都能够,相对无法清零!

  不要在CDQ里面套sort,太慢辣!(一定进不了第一版的!)