CDQ分治总结

CDQ分治

基础知识

CDQ分治的优缺点：

( 1 )优点：代码量少，常数极小（@树套树），可以降低处理维数。（如果嵌套可以大段蒯）
( 2 )缺点：必须离线处理

本质：

分治，只考虑 [L,mid]中元素对 [mid+1,R] 中元素的影响
(这意味着左边只修改，右边只统计答案，不会证正确性）

写法:

据说写法很多，但我只会一种。。。
最后一维

step 1:分治
step 2:边处理边归并排序（左边插入，把能影响当前答案的插完后统计一个右边答案）
step 3:复原（清零）

前面几维

step 1:分治
step 2:排序（归并排序)
step 3:往下一维CDQ

关于使用

一层CDQ有时可以代替一层数据结构
如何CDQ套CDQ？
留坑，到时候yy一下结构和分治的时机

例题

T1

Luogu3368 【模板】树状数组 2
第一维排序，第二维CDQ
懒得打了，蒯下面那个板板就成

T2

Luogu3810 【模板】三维偏序（陌上花开）
第一维排序，第二维CDQ，第三维值域树状数组
（理论上可以打两层CDQ，但常数大）
贴个板板养眼，不记得背背就成

il void CDQ(re int L,re int R)
{
  if(L==R) return;
  re int mid=L+R>>1;
  CDQ(L,mid);CDQ(mid+1,R);
  re int l=L,r=mid+1,top=L-1;
  while(l<=mid&&r<=R)
    {
      if(q[l].b<=q[r].b) add(q[l].c,q[l].num),q1[++top]=q[l++];//三维偏序优先左边，因此一定要加等号
      else q[r].ans+=Query(q[r].c),q1[++top]=q[r++];
    }
  while(l<=mid) q1[++top]=q[l++];
  while(r<=R) q[r].ans+=Query(q[r].c),q1[++top]=q[r++];
  fp(i,L,mid) Clear(q[i].c);fp(i,L,R) q[i]=q1[i];
}

Update：友情附赠树套树版本

// luogu-judger-enable-o2
#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#define ll long long
#define re register
#define il inline
#define fp(i,a,b) for(re int i=a;i<=b;i++)
#define fq(i,a,b) for(re int i=a;i>=b;i--)
using namespace std;
const int N=5e5+100;
struct node
{
  int a,b,c,s,ans;
  bool operator < (const node &o) const {return a<o.a||(a==o.a&&b<o.b)||(a==o.a&&b==o.b&&c<o.c);}
  bool operator == (const node &o) const {return a==o.a&&b==o.b&&c==o.c;}
}q[N],a[N];
struct seg{int ls,rs,s,sum;}t[N*20];
int n,k,top,ans[N],tot,rt[N];
il int gi()
{
  re int x=0,t=1;
  re char ch=getchar();
  while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
  if(ch=='-') t=-1,ch=getchar();
  while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  return x*t;
}
il void Modify(re int &x,re int l,re int r,re int p,re int w)
{
  if(!x) x=++tot;t[x].sum+=w;
  if(l==r) return;
  re int mid=l+r>>1;
  if(p<=mid) Modify(t[x].ls,l,mid,p,w);else Modify(t[x].rs,mid+1,r,p,w);
}
il int Query(re int x,re int l,re int r,re int ql,re int qr)
{
  if(!x||(ql<=l&&r<=qr)) return t[x].sum;
  re int mid=l+r>>1,res=0;
  if(ql<=mid) res=Query(t[x].ls,l,mid,ql,qr);
  if(qr>mid) res+=Query(t[x].rs,mid+1,r,ql,qr);
  return res;
}
int main()
{
  n=gi();k=gi();
  fp(i,1,n) q[i]=(node){gi(),gi(),gi(),1};
  sort(q+1,q+1+n);
  fp(i,1,n)
    if(q[i]==a[top]) a[top].s++;
      else a[++top]=q[i];
  fp(i,1,top)
    {
      for(re int j=a[i].b;j;j-=j&-j) a[i].ans+=Query(rt[j],1,k,1,a[i].c);
      ans[a[i].ans+a[i].s-1]+=a[i].s;
      for(re int j=a[i].b;j<=k;j+=j&-j) Modify(rt[j],1,k,a[i].c,a[i].s);
    }
  fp(i,0,n-1) printf("%d\n",ans[i]);
  return 0;
}

T2

CJOJ2616 - 【HZOI 2016】偏序 I
要求四维偏序？？？
第一维排序，第二维CDQ，第三维CDQ，第四维值域树状数组
要实现CDQ的嵌套，只需在弄前几维CDQ时打个标记，标明它在这次CDQ中是在左边还是在右边处理的。往后到最后一维时，只有标记全为左才能修改，只有标记全为右才能统计进答案。
还有，前几维CDQ只用打标记和归并、分治就成了（所以几乎一模一样，可以直接蒯、再改一改q后的数字），什么修改、统计答案都是最后一维的事。
板子放下面

T3

CJOJ2375 - 【HZOI 2015】偏序 II
要求五维偏序？？？
第一维排序，第二到四维CDQ，第五维值域树状数组

il void CDQ3(re int L,re int R)
{
    if(L==R) return;
    re int mid=L+R>>1;
    CDQ3(L,mid);CDQ3(mid+1,R);
    re int top=L,l=L,r=mid+1;
    while(l<=mid&&r<=R)
    {
        if(q2[l].d<q2[r].d) //......
        {
            if(!q2[l].tag&&!q2[l].tag1) add(q2[l].e);
            q3[top++]=q2[l++];
        }
        else 
        {
            if(q2[r].tag&&q2[r].tag1) ans+=Query(q2[r].e);
            q3[top++]=q2[r++];
        }
    }
    while(l<=mid) q3[top++]=q2[l++];//一一对应关系的结束，标志着左边再不能对右边造成影响
    while(r<=R) 
    {
        if(q2[r].tag&&q2[r].tag1) ans+=Query(q2[r].e);//...
        q3[top++]=q2[r++];
    }
    fp(i,L,R) 
    {
        if(!q2[i].tag&&!q2[i].tag1) Clear(q2[i].e);
        q2[i]=q3[i];
    }
}
il void CDQ2(re int L,re int R)
{
    if(L==R) return;
    re int mid=L+R>>1;
    CDQ2(L,mid);CDQ2(mid+1,R);
    re int top=L,l=L,r=mid+1;
    while(l<=mid&&r<=R)
    {
        if(q1[l].c<q1[r].c) q1[l].tag1=0,q2[top++]=q1[l++];
        else q1[r].tag1=1,q2[top++]=q1[r++];
    }
    while(l<=mid) q1[l].tag1=0,q2[top++]=q1[l++];
    while(r<=R) q1[r].tag1=1,q2[top++]=q1[r++];
    fp(i,L,R) q1[i]=q2[i];
    CDQ3(L,R);
}
il void CDQ1(re int L,re int R)
{
    if(L==R) return;
    re int mid=L+R>>1;
    CDQ1(L,mid);CDQ1(mid+1,R);
    re int top=L,l=L,r=mid+1;
    while(l<=mid&&r<=R)
    {
        if(q[l].b<q[r].b) q[l].tag=0,q1[top++]=q[l++];
        else q[r].tag=1,q1[top++]=q[r++];
    }
    while(l<=mid) q[l].tag=0,q1[top++]=q[l++];
    while(r<=R) q[r].tag=1,q1[top++]=q[r++];//归并排序???
    fp(i,L,R) q[i]=q1[i];
    CDQ2(L,R);
}

然后因常数过大而被其它做法暴踩