晚上午后夜间的频率完全不同啊,  清晨午后夜晚的作用完全不雷同啊亿万先生:

前言

  那是一波狠毒总括。

  上边是一波瞎频仍。

  这几天做了几道CDQ/全部二分,感觉自身做题速度好慢啊。

  很多很显然的事物都看不出来
分治分不出来 打不出来 调不对

  下午午后夜晚的功效完全分裂啊。

  完蛋.jpg 绝望.jpg。

 

前言

  那是一波粗犷统计。

  上边是一波瞎再三。

  这几天做了几道CDQ/全部二分,感觉温馨做题速度好慢啊。

  很多很明朗的事物都看不出来
分治分不出去 打不出去 调不对

  早晨早上晚上的频率完全差异啊。

  完蛋.jpg 绝望.jpg。

 

关于CDQ分治

  CDQ分治,求的是三维偏序难点都清楚的。

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

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

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

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

  瞩目:只总括左侧的操作对左侧的问询的孝敬!

  然后左右两边递归处理就好了。

  正确性:依照线段树的模样递归的CDQ分治,保障每一对长富组在线段树上都有且仅有3个LCA(这不废话吗),而这一组答案就会且仅会在LCA处总结。如若在LCA下边,点对不在1个work内自然不会一个钱打二十五个结。假诺在LCA下边了,点对就在同一侧,不会相互更新。

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

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

  一般是如此的老路:假若三维偏序分别为a,b,c;

  在main函数里保险a递增。

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

  然后分治完左右两边后,需保障左右两边分别b都以一日千里的(a不主要)。

  然后正是相近归并排序的操作了。

  此时左手的a肯定都自愧不如右侧的a,那么一旦对于2个左侧的元素

  以前好像归并的操作就足以保险拥有小于b的左侧的因素都曾经遍历过。

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

  然后你如此归并了一波后,就发现计算完答案后b是稳步递增的了(这一个时候a已经不重庆大学了)。

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

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

  好吧BZOJ动态逆序对,之前写过的,做五回CDQ就好了。

  BZOJ稻草人,也是CDQ。

 

再有二个便是高维偏序难点。

cogs上的2479 HZOI2014 偏序
正是四维偏序板子。

末尾还有七个狠抓版,到了七维,不是CDQ干的业务,详情请见这个PPT

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

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

有个很妙的博客:Candy?

率先在外侧遵照a排好序。

进第1层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

 

 

 

 

关于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,那么只要对于2个出手的要素

  此前类似归并的操作就足以确认保障全数小于b的右侧的成分都早已遍历过。

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

  然后您这么归并了一波后,就意识总括完答案后b是雷打不动递增的了(这些时候a已经不根本了)。

  对于上层操作,符合”左右两边分别b是一日千里的”了。

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

  好吧BZOJ动态逆序对,此前写过的,做四次CDQ就好了。

  BZOJ稻草人,也是CDQ。

 

还有1个正是高维偏序难题。

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)都低于它” =
三维偏序。

复制到另1个数组里再做一遍cdq就足以了。

复杂度O(nlog^3n)。

 

亿万先生: 3亿万先生: 4

#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))就越发。

  大致便是如此1个东西。

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

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

  一样的覆辙了。

 

至于全体二分

  整体二分首假诺把富有询问放在一块儿二分答案,然后把操作也一同分治。

  哪天用吧?

  当你意识多组通晓能够离线的时候

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

  当您发觉询问的操作都以一律的的时候

  你就能够采用完全二分那么些东西了。

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

  想想:二分答案的时候,对于二个答案,是还是不是多少操作是没用的,有个别操作贡献是不变的?

  比如二分3个时日,那么时间前面产生的操作正是从未用的,时间前边的进献是不变的。

  二分二个最大值,比mid大的都以没用的,比mid小的个数是任其自然的。

  全体二分正是行使了这么1天性子。

  二分答案,然后把没有用的操作扫进左侧,和答案在[mid+1,r]的了然一起递归处理。

  把有效的操作放进右边,减去不变的进献,和答案在[l,mid]的协同递归处理。

  留意答案在[mid+1,r]的垂询要算上放进了右侧的操作的孝敬,开个变量记下来/直接压缩都得以。

  注意整体二分在solve内的复杂度一定只好与区间长度线性相关,不能够每一趟都有别的复杂度!

  比如1次solve的复杂度是O(lenlogn)就足以,O(len+sqrt(n))就非凡。

  大致正是如此二个事物。

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

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

  一样的套路了。

 

有关部分要留心的地点

  归并自然要把剩下的搞完!每回自小编都遗忘那码子事!

  树状数组不可能暴力清零!记个time或许依葫芦画瓢减回去都足以,一定无法清零!

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

 

有关部分要留意的地点

  归并肯定要把多余的搞完!每趟小编都记不清那码子事!

  树状数组无法暴力清零!记个time恐怕依葫芦画瓢减回去都能够,一定无法清零!

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

 

相关文章

网站地图xml地图