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

喵(ฅ>ω<*ฅ)

1 条评论

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

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

发表评论

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

你是机器人吗? =。= *