题解说明

问题背景：
给定一个 $2 \times n$ 的排列矩阵（即 $1 \sim 2n$ 的数被放在两行 $n$ 列的网格中），要求统计某种与相邻关系、对称关系相关的计数结果。参数 $k$ 控制统计的维度。程序通过线段树维护区间最小值及其分布，逐步扫描元素并更新答案。

核心思路：

1. 数据结构设计：

• 使用线段树维护区间最小值 $mn[p]$ 及其对应的统计数组 $tr[p][i]$。
• $tr[p][i]$ 表示在该区间内，最小值加上偏移 $i$ 的位置数量。
• 懒标记 $add[p]$ 用于区间加操作。

2. 线段树操作：

• build：初始化，每个叶子节点 $tr[p][0] = 1$，表示长度为 $1$。
• mdf：对区间加上 $v$，更新懒标记与最小值。
• up：合并左右子树，保证父节点的最小值与统计数组正确。

3. 主循环处理：

• 按照数值从 $1$ 到 $2n$ 的顺序扫描。
• 对于当前数 $i$，找到其所在的行列 $(x,y)$。
• 将位置 $i$ 标记为已处理（$mdf(i,i,-\infty)$），并对 $[1,i]$ 区间整体加 $1$。
• 根据题意关系，对对称位置、相邻位置进行 wk() 调整（即调用 mdf 更新）。
• wk() 的逻辑：若对象集合的最大值 $\leq r$，则对 $[1,l]$ 区间加上 $v$，其中 $l$ 是集合最小值。
• 最后，将线段树根节点的统计数组累加到答案 res 中。

4. 结果统计：

• 每次循环后，根节点 $mn[1]$ 表示全局最小值，$tr[1][j]$ 表示对应偏移的数量。
• 将这些数量累加到 res。
• 最终对 $res[0]$ 做一次特殊处理：$res[1] += res[0]$。
• 输出 $res[1..k]$。

复杂度分析：

• 每次操作涉及 $O(\log n)$ 的线段树更新。
• 总体复杂度 $O(n \log n)$，适合 $n \leq 2 \times 10^5$

#include <bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);++i)  // 正向循环宏
#define Rep(i,a,b) for(int i=(a);i>=(b);--i)  // 反向循环宏
using namespace std;

#define maxn 200005  // 数组最大长度
#define inf 0x3f3f3f3f  // 表示无穷大的值

int n, k;  // n是基础尺寸，k是问题相关的参数
int a[2][maxn];  // 二维数组存储数据，可能表示某种网格结构
int px[maxn], py[maxn];  // 记录某个值所在的坐标(x,y)
long long res[maxn];  // 存储最终结果

// 线段树相关数组
// tr[p][i]：节点p的第i个统计值
// mn[p]：节点p维护的最小值
// add[p]：节点p的懒惰标记（用于区间加操作）
int tr[maxn << 2][13], mn[maxn << 2], add[maxn << 2];

// 线段树向上更新函数：用子节点信息更新父节点
void up(int p) {
    int ls = p << 1, rs = p << 1 | 1;  // 左子节点和右子节点

    // 确保左子节点是较小值的那一侧
    if (mn[ls] > mn[rs])
        swap(ls, rs);

    // 更新父节点的最小值（加上当前节点的懒惰标记）
    mn[p] = mn[ls] + add[p];
    // 复制较小值子节点的统计信息
    For(i, 0, k)tr[p][i] = tr[ls][i];
    // 合并较大值子节点的统计信息（考虑偏移量）
    For(i, 0, k - (mn[rs] - mn[ls]))
        tr[p][i + (mn[rs] - mn[ls])] += tr[rs][i];
}

// 线段树构建函数
void build(int p, int l, int r) {
    mn[p] = inf;  // 初始化最小值为无穷大
    tr[p][0] = r - l + 1;  // 初始化统计值：区间长度

    if (l == r)  // 叶子节点，无需继续递归
        return;

    int mid = l + r >> 1;  // 计算中点
    build(p << 1, l, mid);  // 构建左子树
    build(p << 1 | 1, mid + 1, r);  // 构建右子树
}

// 线段树区间更新函数：对[nl, nr]区间加上v
void mdf(int p, int l, int r, int nl, int nr, int v) {
    // 当前区间完全在更新区间内
    if (l >= nl && r <= nr) {
        add[p] += v;  // 更新懒惰标记
        mn[p] += v;   // 更新最小值
        return;
    }

    int mid = l + r >> 1;  // 计算中点

    // 递归更新左子树
    if (nl <= mid)
        mdf(p << 1, l, mid, nl, nr, v);
    // 递归更新右子树
    if (nr > mid)
        mdf(p << 1 | 1, mid + 1, r, nl, nr, v);

    up(p);  // 更新当前节点信息
}

// 处理一组操作的函数
// r: 当前位置，o: 操作对象列表，v: 操作值
void wk(int r, vector<int> o, int v) {
    // 找到对象列表中的最小值和最大值
    int l = *min_element(o.begin(), o.end());
    int mx = *max_element(o.begin(), o.end());

    // 如果最大值不超过当前位置，则执行区间更新
    if (mx <= r)
        mdf(1, 1, n * 2, 1, l, v);
}

signed main() {
    cin >> n >> k;  // 输入n和k

    // 输入数据并记录每个值的坐标
    For(i, 0, 1)
        For(j, 0, n - 1) {
            cin >> a[i][j];
            px[a[i][j]] = i;  // 记录x坐标
            py[a[i][j]] = j;  // 记录y坐标
        }

    build(1, 1, n * 2);  // 构建线段树

    // 主循环处理每个元素
    For(i, 1, n * 2) {
        int x = px[i], y = py[i];  // 获取当前元素的坐标

        // 更新线段树：将位置i的值设为负无穷（可能表示已处理）
        mdf(1, 1, n * 2, i, i, -inf);
        // 更新线段树：对[1,i]区间加1
        mdf(1, 1, n * 2, 1, i, 1);

        // 处理对称位置的元素（x坐标相反，y坐标相同）
        wk(i, {a[!x][y]}, -1);

        // 处理相邻y坐标的情况（左右邻居）
        for (int yy : {(y + 1) % n, (y + n - 1) % n}) {
            wk(i, {a[x][yy]}, -1);  // 处理同x不同y的邻居
            // 处理多种组合的邻居
            wk(i, {a[x][yy], a[!x][yy], a[!x][y]}, 1);
        }

        // 统计结果：将线段树中的统计信息累加到结果数组
        For(j, 0, k - mn[1])
            res[mn[1] + j] += tr[1][j];
    }

    res[1] += res[0];  // 特殊处理：将res[0]累加到res[1]

    // 输出结果
    For(i, 1, k)
        cout << res[i] << " ";

    return 0;
}