CDQ分治

题目链接 : stars
本题是个四维偏序问题：时间,x,y,z。用CDQ分治来解决。而一个CDQ能解决三维偏序问题，四维偏序问题就需要两次CDQ分治。首先第一个CDQ帮助我们解决了 二维 的顺序，还需要再来一个CDQ解决剩下的三维偏序。
首先原序列按照时间已经排好序了，我们需要这样的CDQ分治结构。

//在进入这个CDQ2分治前已经保证时间和x是有序的了,即是已经保证了时间和x都是递增的
void CDQ2()
{
    这里就是一个正常的三维偏序了;
    按照y合并;
    按照z处理询问;
}
void CDQ1(int l , int r)
{
    CDQ1(l,mid);
    CDQ1(mid+1,r);
    将左边的修改和右边的询问按照x顺序合并，用于接下来的CDQ2使用;
    CDQ2(l,r);//这个CDQ用于处理三维偏序，即处理左边的修改和右边的询问
    按照x合并;
}

时间复杂度为$O(nlog^{3}n)$
代码:

#include <bits/stdc++.h>
#define eps 1e-6
#define ls (rt << 1)
#define rs (rt << 1 | 1)
#define lowbit(x) (x & (-x))
#define SZ(v) ((int)(v).size())
#define All(v) (v).begin(), (v).end()
#define mp(x, y) make_pair(x, y)
#define fast ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;
const int N = 4e5 + 10;
const int M = 1e7 + 10;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
const int INF = 2e9;
int n, m, ans[N], q[N], Z[N] , c[N];
struct node
{
    int x, y, z, op, id;
} star[N], star1[N], star2[N];
void add(int x, int v)
{
    for (; x <= m; x += lowbit(x))
        c[x] += v;
}
int ask(int x)
{
    int res = 0;
    for (; x > 0; x -= lowbit(x))
        res += c[x];
    return res;
}
void cdq2(int l, int r)
{
    if( l >= r) return ;
    int mid = (l + r) >> 1;
    cdq2(l,mid);
    cdq2(mid+1,r);
    int tot1 = l , i = l;
    for(int j = mid + 1; j <= r; ++ j) {
        if(star1[j].op != 0){
            while(i <= mid && star1[i].y <= star1[j].y){
                if(!star1[i].op) add(star1[i].z , 1);
                ++ i;
            }
            ans[star1[j].id] += star1[j].op * ask(star1[j].z);
        }
    }
    for(int k = l; k < i; ++ k) if(!star1[k].op) add(star1[k].z , -1);
    /*merge by y*/
    i = l;
    for(int j = mid + 1; j <= r; ++ j) {
        while(i <= mid && star1[i].y <= star1[j].y){ star2[tot1 ++] = star1[i]; ++ i; }
        star2[tot1 ++] = star1[j];
    }
    for(;i<=mid; ++i) star2[tot1 ++] = star1[i];
    for(int k = l; k <= r; ++ k) star1[k] = star2[k];
}
void cdq1(int l, int r)
{
    if (l >= r)
        return;
    int mid = (l + r) >> 1;
    cdq1(l, mid);
    cdq1(mid + 1, r);
    int tot1 = 0 , i = l;
    for(int j = mid + 1; j <= r; ++ j) {
        if(star[j].op != 0){
            while(i <= mid && star[i].x <= star[j].x){
                if(!star[i].op) star1[++ tot1] = star[i];
                ++ i;
            }
            star1[++ tot1] = star[j];
        }
    }
    cdq2(1, tot1);
    /*merge by x*/
    i = l;
    tot1 = l;
    for(int j = mid + 1; j <= r; ++ j) {
        while(i <= mid && star[i].x <= star[j].x) { star1[tot1 ++] = star[i]; ++ i;}
        star1[tot1 ++] = star[j];
    }
    for(;i <= mid; ++i) star1[tot1 ++] = star[i];
    for(int k = l; k <= r; ++ k) star[k] = star1[k];
}
int main()
{
    int T, Q, op, x1, x2, y1, y2, z1, z2;
    scanf("%d", &T);
    while (T--)
    {
        int tot = 0;
        m = 0;
        scanf("%d", &Q);
        for (int i = 1; i <= Q; ++i)
        {
            q[i] = 0;
            ans[i] = 0;
            scanf("%d", &op);
            if (op == 1)
            {
                scanf("%d%d%d", &x1, &y1, &z1);
                Z[++ m] = z1;
                star[++tot] = node{x1, y1, z1, 0, i};
            }
            else
            {
                q[i] = 1;
                scanf("%d%d%d", &x1, &y1, &z1);
                scanf("%d%d%d", &x2, &y2, &z2);
                Z[++ m] = z1 - 1;
                Z[++ m] = z2;
                star[++tot] = node{x2, y2, z2, 1, i};
                star[++tot] = node{x1 - 1, y1 - 1, z2, 1, i};
                star[++tot] = node{x1 - 1, y2, z1 - 1, 1, i};
                star[++tot] = node{x2, y1 - 1, z1 - 1, 1, i};

                star[++tot] = node{x1 - 1, y2, z2, -1, i};
                star[++tot] = node{x2, y1 - 1, z2, -1, i};
                star[++tot] = node{x2, y2, z1 - 1, -1, i};
                star[++tot] = node{x1 - 1, y1 - 1, z1 - 1, -1, i};
            }
        }
        sort(Z + 1, Z + m + 1);
        m = unique(Z + 1, Z + m + 1) - Z - 1;
        for (int i = 1; i <= tot; ++i){
            star[i].z = lower_bound(Z + 1, Z + m + 1, star[i].z) - Z;
        }
        cdq1(1, tot);
        for (int i = 1; i <= Q; ++i)
        {
            if (q[i])
                printf("%d\n", ans[i]);
        }
    }
    return 0;
}

cpp