【题解】从四维偏序到六维偏序 ——quhengyi11

失 (wen) 踪 (hua) 人 (ke) 口 (gu) 回 (gu) 归 (gu)

前置技能：cdq 分治（我觉得这个站的人水平辣么高肯定都会 QAQ）

那么我们开始上四维偏序吧（cdq 套一只 cdq）

例题：偏序

首先，我们有 n 个可爱的四元组 $(a,b,c,d)$，我们想着怎样才能输出来四维偏序有多少对呢？

显然我们需要把 a 先排个序，然后用 cdq 惯用套路，用左边的给右边算贡献。

我们可以发现，我们不会做了。

想想我们搞三维偏序的时候怎么搞的，我们先将第一维排序，第二维用 cdq 分治左边贡献右边，第三位用树状数组维护才勉强弄好，你现在再给我加一维我又怎么办呢？

我们可以先假装 a 不存在，那么我们 cdq 分治的时候只需要先给 b 排序，然后双指针划 c 过去顺便树状数组维护 d 就行了。

那 a 回来了，我们只能鏼鏼发抖吗？

我们可以先将 a 排个序，将它分为 left(贡献答案)，right(统计答案) 两部分，这样我们就规定了每个 a 的职责，不是贡献就是统计，我们此时可以进入 b，还是一如既往地给 b 排序，此时 a 虽然是乱序，可是只要根据 a 原本的职责来履行，答案依旧是正确的（想一想为什么），我们将在 b 排好序后在左边的称为 left，在右边的称为 right，那么贡献答案的只有可能是 b 为 left 的数，统计答案的也只有可能是 b 为 right 的数，也就是说，只有 a,b 同时为 left 的时候才能贡献答案，a,b 同时为 right 才能统计答案，然后步骤几乎是一样的，双指针将 c 划过去，给 d 算贡献。

至于如何记录 a,b 为 left 还是 right，我们不必开一个临时数组记录，可以直接记录分界点 (代码里的 mid1)，分界点左边的（包括分界点）就是 left，否则就是 right

时间复杂度 $O(nlog^3n)$

代码：

#include<bits/stdc++.h>
#define fo(i, a, b) for (Re int i = (a); i <= (b); ++i)
#define fd(i, a, b) for (Re int i = (a); i >= (b); --i)
#define edge(i, u) for (Re int i = head[u], v = e[i].v; i; i = e[i].nxt, v = e[i].v)
#define N 50005
#define Re register
#define pb push_back
#define F first
#define S second
#define ll long long
#define inf 1000000007
#define mp std::make_pair
#define lowbit(x) (x & -x)
#define ls (k << 1)
#define rs (k << 1 | 1)
#define mod 1000000007
int n, k;
int a[N][5], tmp2[N][5], tmp3[N][5], c[N], ans;
inline void add (int x, int val) {for (Re int i = x; i <= n; i += lowbit(i)) c[i] += val;}
inline int query (int x) {Re int ret = 0; for (Re int i = x; i; i -= lowbit(i)) ret += c[i]; return ret;}
inline void cdq3 (int l, int r, int mid1)//第二维是有序的，当前排序第三维，并且按照类似三维偏序的写法计算贡献
{
    if (l == r) return;
    int mid = l + r >> 1;
    cdq3(l, mid, mid1); cdq3(mid + 1, r, mid1);
    int L = l, R = mid + 1, i = l;
    while (L <= mid && R <= r)
    {
        if (tmp2[L][3] < tmp2[R][3])
        {
            if (tmp2[L][1] <= mid1)
                add(tmp2[L][4], 1);//第四维用树状数组维护, 当前第一维，第二维，第三维都满足序关系
            memcpy(tmp3[i++], tmp2[L++], sizeof tmp2[L]);
        }
        else
        {
            if (mid1 < tmp2[R][1])
                ans += query(tmp2[R][4]);
            memcpy(tmp3[i++], tmp2[R++], sizeof tmp2[R]);
        }
    }
    int upL = L - 1;//前面有多少 L 被加到树状数组里了
    while (L <= mid)
    {
        memcpy(tmp3[i++], tmp2[L++], sizeof tmp2[L]);
    }
    while (R <= r)
    {
        if (mid1 < tmp2[R][1])
            ans += query(tmp2[R][4]);
        memcpy(tmp3[i++], tmp2[R++], sizeof tmp2[R]);
    }
    fo (i, l, upL)//清空树状数组
        if (tmp2[i][1] <= mid1)
            add(tmp2[i][4], -1);
    fo (i, l, r) memcpy(tmp2[i], tmp3[i], sizeof tmp3[i]);
}
inline void cdq2 (int l, int r)//第一维现在是有序的，我们给第一维重标号，然后给第二维排序
{
    if (l == r) return;
    int mid = l + r >> 1;
    int mid1 = a[mid][1];//用记录第一维最中间的值来重标号，减少复杂度
    cdq2(l, mid); cdq2(mid + 1, r);
    int L = l, R = mid + 1, i = l;
    while (L <= mid && R <= r)
    {
        if (a[L][2] < a[R][2])
        {
            memcpy(tmp2[i++], a[L++], sizeof a[L]);
        }
        else
        {
            memcpy(tmp2[i++], a[R++], sizeof a[R]);
        }
    }
    while (L <= mid)
        memcpy(tmp2[i++], a[L++], sizeof a[L]);
    while (R <= r)
        memcpy(tmp2[i++], a[R++], sizeof a[R]);
    fo (i, l, r) memcpy(a[i], tmp2[i], sizeof a[i]);//当前第二维是有序的，并且第一维小于等于 mid1 的值是更新值，大于 mid1 的值是查询值
    cdq3(l, r, mid1);
}
int main ()
{
//  freopen("partial_order.in", "r", stdin);
//  freopen("partial_order.out", "w", stdout);
    scanf("%d", &n);
    k = 4;
    fo (i, 1, n)
    {
        a[i][1] = i;
        scanf("%d", &a[i][2]);
    }
    fo (i, 1, n) scanf("%d", &a[i][3]);
    fo (i, 1, n) scanf("%d", &a[i][4]);
    cdq2(1, n);
    printf("%d\n", ans);
    return 0;
}

然而，当一个毒瘤出题人将维数加到四维以上的时候，因为时间复杂度 log 太多，代码自闭了。

此时就要请出我们的毒瘤 bitset 压位大法了。

例题：偏序++

易知，对于每个数，当且仅当另一个数 x 比它对应位数都小（或等于）的时候，这两个数可以组成一个偏序对，换言之，就是将第 i 个维度小于等于当前这个数的第 i 个维度的数取一个交集 (1<=i<=k)，然后数交集里有多少个数，最后减去自己一个，就是这个数的答案了。

然而这时我们需要一个 N×K×N 的 bitset 数组，然而 N=40000, K=6 的时候空间显然是不够的，我们可以分块处理然后在统计答案的时候用根号 N 的时间统计即可。

总时间复杂度就是 $O((KN\sqrt N+N^2)/一个大常数)$

代码:

#include<bits/stdc++.h>
#define fo(i, a, b) for (R int i = (a); i <= (b); ++i)
#define fd(i, a, b) for (R int i = (a); i >= (b); --i)
#define edge(i, u) for (R int i = head[u], v = e[i].v; i; i = e[i].nxt, v = e[i].v)
#define N 40005
#define R register
#define pb push_back
#define F first
#define S second
#define ll long long
#define inf 1000000007
#define mp std::make_pair
#define lowbit(x) (x & -x)
#define ls (k << 1)
#define rs (k << 1 | 1)
#define mod 1000000007
int n, k, sq, pre[205], suf[205], sum, t[8][N], c, bl[N + 233], up;
using namespace std;
pair<int, int> a[8][N];
bitset<N> b[8][205], now, ans;
int main ()
{
    freopen("partial_order_plus.in", "r", stdin);
    freopen("partial_order_plus.out", "w", stdout);
    scanf("%d %d", &n, &k);
    ++k;
    fo (j, 1, n) a[1][j] = mp(t[1][j] = j, j);
    fo (i, 2, k)
        fo (j, 1, n)
        {
            scanf("%d", &a[i][j].F);
            t[i][j] = a[i][j].F;
            a[i][j].S = j;
        }
    sq = (int) 500;
    up = n / sq;
    while (up * sq < n) ++up;
    fo (i, 1, up)
    {
        pre[i] = (i - 1) * sq + 1;
        suf[i] = i * sq;
        fo (j, pre[i], suf[i]) bl[j] = i;
    }
    fo (i, 1, k) sort(a[i] + 1, a[i] + n + 1);
    suf[up] = n;
    fo (i, 1, k)
    {
        fo (j, 1, up)
        {
            b[i][j] = b[i][j - 1];//求前缀并
            fo (k, pre[j], suf[j])
                b[i][j].set(a[i][k].S);
        }
    }
    fo (I, 1, n)
    {
        ans.set();
        fo (i, 1, k)
        {
            int pos = lower_bound(a[i] + 1, a[i] + n + 1, mp(t[i][I], inf)) - a[i] - 1;//当前点该维度在当前维度前有多少个数
            now = b[i][bl[pos] - 1];
            fo (j, pre[bl[pos]], pos)
                now.set(a[i][j].S);
            ans &= now;
        }
        sum += ans.count() - 1;//减掉自己
    }
    printf("%d\n", sum);
    return 0;
}

参考文章：stdcall 小姐姐的文章 QAQ