CDQ分治

流程：

• 递归左区间
• 处理左区间修改对右区间询问的影响
• 递归右区间
• 合并信息

需要注意的通常需要反复按照不同规则排序以消除影响。

引入：

三（二）维LIS问题

时间轴、x轴、y轴

#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 100010
using namespace std;
struct data
{
    int p , x , y , dp;
}a[N];
int n , f[N] , v[N];
bool cmp1(data a , data b)
{
    return a.x < b.x;
}
bool cmp2(data a , data b)
{
    return a.p < b.p;
}
void add(int x , int a)
{
    int i;
    for(i = x ; i <= n ; i += i & -i) f[i] = max(f[i] , a);
}
int query(int x)
{
    int i , ans = 0;
    for(i = x ; i ; i -= i & -i) ans = max(ans , f[i]);
    return ans;
}
void clear(int x)
{
    int i;
    for(i = x ; i <= n ; i += i & -i) f[i] = 0;
}
void solve(int l , int r)
{
    if(l >= r) return;
    int mid = (l + r) >> 1 , p1 = l , p2 = mid + 1 , i;
    solve(l , mid) , sort(a + l , a + mid + 1 , cmp1) , sort(a + mid + 1 , a + r + 1 , cmp1);
    while(p2 <= r)
    {
        if(p1 <= mid && a[p1].x < a[p2].x) add(a[p1].y , a[p1].dp) , p1 ++ ;
        else a[p2].dp = max(a[p2].dp , query(a[p2].y - 1) + 1) , p2 ++ ;
    }
    for(i = l ; i <= mid ; i ++ ) clear(a[i].y);
    sort(a + mid + 1 , a + r + 1 , cmp2) , solve(mid + 1 , r);
}
int main()
{
    int i , ans = 0;
    scanf("%d" , &n);
    for(i = 1 ; i <= n ; i ++ ) scanf("%d%d" , &a[i].x , &a[i].y) , a[i].p = i , v[i] = a[i].y , a[i].dp = 1;
    sort(v + 1 , v + n + 1);
    for(i = 1 ; i <= n ; i ++ ) a[i].y = lower_bound(v + 1 , v + n + 1 , a[i].y) - v;
    solve(1 , n);
    for(i = 1 ; i <= n ; i ++ ) ans = max(ans , a[i].dp);
    printf("%d\n" , ans);
    return 0;
}

三维偏序问题

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
struct flower{
    int x,y,z;
    int cnt,ans;
}d[1000010];
int tree[3000010],n,k,tot,num[1000010];
int tmp(flower a,flower b)
{
    if(a.x<b.x) return 1;
    if(a.x>b.x) return 0;
    if(a.y<b.y) return 1;
    if(a.y>b.y) return 0;
    if(a.z<b.z) return 1;
    return 0;
}
int cmp(flower a,flower b)
{
    if(a.y<b.y) return 1;
    if(a.y>b.y) return 0;
    if(a.z<b.z) return 1;
    if(a.z>b.z) return 0;
    if(a.x<b.x) return 1;
    return 0;
}
inline int lowbit(int x)
{
    return x&(-x);
}
inline void updata(int x,int v)
{
    while(x<=k)
     {
        tree[x]+=v;
        x+=lowbit(x);
     }
    return;
}
inline int ask(int x)
{
    int sum=0;
    while(x)
     {
        sum+=tree[x];
        x-=lowbit(x);
     }
    return sum;
}
void CDQ(int l,int r)
{
    if(l==r)
     {
        d[l].ans+=d[l].cnt-1;
        return;
     }
    int mid=(l+r)>>1;
    CDQ(l,mid);
    sort(d+l,d+mid+1,cmp);
    sort(d+mid+1,d+r+1,cmp);
    int j=l;
    for(int i=mid+1;i<=r;++i)
     {
        while(j<=mid&&d[j].y<=d[i].y)
           updata(d[j].z,d[j].cnt),++j;
        d[i].ans+=ask(d[i].z);
     }
    for(int i=l;i<j;++i) updata(d[i].z,-d[i].cnt);
    sort(d+mid+1,d+r+1,tmp);
    CDQ(mid+1,r);
}
int main()
{
    int i,j;
    scanf("%d%d",&n,&k);
    for(i=1;i<=n;++i) scanf("%d%d%d",&d[i].x,&d[i].y,&d[i].z),d[i].ans=1;
    sort(d+1,d+n+1,tmp);
    for(i=1;i<=n;++i)
     if(i!=1&&d[i].x==d[i-1].x&&d[i].y==d[i-1].y&&d[i].z==d[i-1].z) d[tot].cnt++;
      else d[++tot]=d[i],d[tot].cnt=1;
    CDQ(1,tot);
    sort(d+1,d+tot+1,tmp);
    for(i=1;i<=tot;++i) num[d[i].ans]+=d[i].cnt;
    for(i=1;i<=n;++i) printf("%d\n",num[i]);
    return 0;
}

离线问题相关：

伪强制在线： Codeforces 1217F —— 线段树分治

记录所有可能的操作，解码决定是否执行。

数据结构问题：时间轴，操作空间。

时间轴：自动有序
在线：k维数据结构维护k维空间
离线：处理左区间对右区间的影响，分治结构保证了“相对有序”。可以对另一维进行排序。用k-1维数据结构维k维空间即可。
上述过程可以反复嵌套直至便于实现。

整体二分：
[POI2011]MET-Meteors

#include <cmath>
#include <queue>
#include <cstdio>
#include <vector>
#include <iomanip>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 300010
#define ll long long
#define inf 1000000000
using namespace std;
char xB[1<<15],*xS=xB,*xT=xB;
#define getchar() (xS==xT&&(xT=(xS=xB)+fread(xB,1,1<<15,stdin),xS==xT)?0:*xS++)
inline int read() 
{ 
    int x=0,f=1;char ch=getchar(); 
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} 
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} 
    return x*f; 
}
int n,m,k,p[N],l[N],r[N],v[N],ans[N],T;
int d[N],tmp[N];
bool ck[N];
vector<int> a[N];
ll c[N];
int add(int x,int v)
{
    for(;x<=m;x+=x&(-x))
    c[x]+=v;
}
ll ask(int x)
{
    ll ret=0;
    for(;x;x-=x&(-x))
    ret+=c[x];
    return ret;
}
void cal(int x,int f)
{
    if(l[x]<=r[x])
    add(l[x],v[x]*f),add(r[x]+1,-v[x]*f);
    else add(1,v[x]*f),add(r[x]+1,-v[x]*f),add(l[x],v[x]*f);
}
void solve(int l,int r,int L,int R)//处理 l~r国家 答案区间L~R 
{
    if(l>r)return ;
    if(L==R)
    {
        for(int i=l;i<=r;i++)
        ans[d[i]]=L;
        return ;
    }
    int mid=(L+R)>>1;
    while(T<=mid)T++,cal(T,1);
    while(T>mid)cal(T,-1),T--;
    int cnt=0;
    for(int i=l;i<=r;i++)
    {
        ll ret=0;
        for(int j=0;j<a[d[i]].size();j++)
        {
            ret+=ask(a[d[i]][j]);
            if(ret>=p[d[i]])break ;
        }
        if(ret>=p[d[i]])ck[d[i]]=1,cnt++;
        else ck[d[i]]=0;
    }
    int l_=l,r_=l+cnt;
    for(int i=l;i<=r;i++)
    {
        if(ck[d[i]])tmp[l_++]=d[i];
        else tmp[r_++]=d[i];
    }
    for(int i=l;i<=r;i++)d[i]=tmp[i];
    solve(l,l_-1,L,mid);solve(l_,r_-1,mid+1,R);
}
int main()
{
    n=read(),m=read();
    for(int i=1;i<=m;i++)
    {
        int x=read();
        a[x].push_back(i);
    }
    for(int i=1;i<=n;i++)
    p[i]=read(),d[i]=i;
    k=read();
    for(int i=1;i<=k;i++)
    l[i]=read(),r[i]=read(),v[i]=read();
    l[++k]=1,r[k]=m,v[k]=inf;
    solve(1,n,1,k);
    for(int i=1;i<=n;i++)
    printf(ans[i]==k?"NIE\n":"%d\n",ans[i]);
}