威尼斯人娱乐晚上早上早晨的频率完全不雷同啊

前言

  那是一波强行计算。

  上边是一波瞎每每。

  如今做了几道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,太慢辣!(一定进不了第一版的!)

 

相关文章