题意

有一个两个长度为 $n$ 的排列，定义种类 $x$ 的线是连接第一个排列和第二排列中值为 $x$ 大的两个位置的线。求无序数对 $(i,j)$ 的个数，要满足 $i$ 的线和 $j$ 的线相交，且 $|i-j| > k$。

$1 \le n \le 10^5,0 \le k < n$。

分析

设 $x_i$ 表示 $i$ 在排列 $a$ 中的位置，$y_i$ 表示 $i$ 在排列 $b$ 中的位置。要让 $i,j$ 的线相交，不妨设 $x_i < x_j$，那么就有 $y_i > y_j$。

现在就是三个限制。

• $x_i < x_j$。
• $y_i > y_j$。
• $|i-j|>k$，即 $i \not \in [j-k,j+k]$。

这三个限制是三位偏序，用 cdq 分治实现即可。

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define il inline
#define N 100005
il int rd(){
    int s = 0, w = 1;
    char ch = getchar();
    for (;ch < '0' || ch > '9'; ch = getchar()) if (ch == '-') w = -1;
    for (;ch >= '0' && ch <= '9'; ch = getchar()) s = ((s << 1) + (s << 3) + ch - '0');
    return s * w;
}
int n, k, a[N], b[N], x[N], y[N], id[N], tr[N], ans;
il bool cmp1(int a, int b){return x[a] < x[b];}
il bool cmp2(int a, int b){return y[a] > y[b];}
il void clr(int x){for (int i = x; i <= n; i += (i & (-i))) tr[i] = 0;}
il void add(int x, int k){for (int i = x; i <= n; i += (i & (-i))) tr[i] += k;}
il int ask(int x){int ans = 0;for (int i = x; i >= 1; i -= (i & (-i))) ans += tr[i];return ans;}
void cdq(int l, int r){
    if (l == r) return ;
    int mid = (l + r) >> 1;
    sort (id + l, id + r + 1, cmp1);
    cdq(l, mid), cdq(mid + 1, r);
    sort (id + l, id + mid + 1, cmp2), sort (id + mid + 1, id + r + 1, cmp2);
    for (int i = l, j = mid + 1; j <= r; j++){
        for (; i <= mid && y[id[i]] > y[id[j]]; i++) add(id[i], 1);
        if (id[j] - k > 1) ans += ask(id[j] - k - 1);
        if (id[j] + k < n) ans += ask(n) - ask(id[j] + k);
    }
    for (int i = l; i <= mid; i++) clr(id[i]);
}
signed main(){
    n = rd(), k = rd();
    for (int i = 1; i <= n; i++) id[i] = i;
    for (int i = 1; i <= n; i++) x[a[i] = rd()] = i;
    for (int i = 1; i <= n; i++) y[b[i] = rd()] = i;
    cdq(1, n);
    printf ("%lld\n", ans);
    return 0;
}