失 (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

分类: 文章

quhengyi11

AFO 有缘再见

1 条评论

B_Z_B_Y · 2018年11月1日 12:04 下午

看来我得去学一下 cdq 分治 QwQ ~~~(:站内最低水平 qwq)~~~

发表评论

电子邮件地址不会被公开。 必填项已用*标注