失 (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
2 条评论