题解

问题分析

题目要求将 ( n ) 根柱子上的 ( n \times m ) 个球（每种颜色 ( m ) 个）重新排列，使每种颜色的球集中在同一根柱子上，且操作次数不超过 ( 820000 )。每次操作仅能移动柱子最上方的球到另一根柱子的最上方，且目标柱子最多有 ( m-1 ) 个球。

核心思路

代码采用 分治策略 结合 缓冲技术 解决问题，核心思想类似于“快速排序的分治思想”：将颜色范围逐步二分，通过递归处理子问题，最终使每种颜色的球集中到单独的柱子上。

1. 分治划分：将颜色范围 ([l, r)) 划分为 ([l, mid)) 和 ([mid, r))，目标是让左半部分柱子（( l \sim mid-1 )）主要存放左半颜色（(< mid)）的球，右半部分柱子（( mid \sim r-1 )）主要存放右半颜色（(\geq mid)）的球。

2. 局部调整（solve函数）：对于每对柱子（左半区的柱子 ( i ) 和右半区的柱子 ( j )），利用缓冲柱（第 ( n ) 根柱子，0-based索引）辅助移动球，分离出左半颜色和右半颜色的球，确保左半柱子优先存放左半颜色，右半柱子优先存放右半颜色。

3. 递归处理：完成当前划分后，递归处理左半范围 ([l, mid)) 和右半范围 ([mid, r))，直至每个子问题的范围缩小到单个颜色（即 ( l+1 = r )），此时该颜色的球已集中到对应柱子上。

详细步骤

1. 分治框架（trav函数）

• 划分颜色范围：对于当前范围 ([l, r))，计算中点 ( mid = (l + r) / 2 )，将颜色分为“左半颜色”（(< mid)）和“右半颜色”（(\geq mid)）。
• 处理柱子对：遍历左半区柱子 ( i \in [l, mid) ) 和右半区柱子 ( j \in [mid, r) )，通过调整使左半柱子尽可能存放左半颜色的球，右半柱子尽可能存放右半颜色的球：
  • 若左半柱子 ( i ) 和右半柱子 ( j ) 中左半颜色的球总数 (\geq m)，则优先将左半颜色的球集中到左半柱子 ( i )。
  • 否则，将右半颜色的球集中到右半柱子 ( j )。
• 递归子问题：对左半范围 ([l, mid)) 和右半范围 ([mid, r)) 重复上述过程，直至每个范围仅含一种颜色。

2. 局部调整（solve函数）

• 缓冲辅助移动：使用缓冲柱（第 ( n ) 根）临时存放球，通过一系列移动操作分离目标颜色（左半或右半颜色）：
  • 先将非目标颜色的球移至缓冲柱或临时柱子，露出目标颜色的球。
  • 将目标颜色的球移至对应柱子（左半柱子或右半柱子）。
  • 最后将非目标颜色的球移回原柱子，确保未处理的球不影响后续操作。
• 记录操作：每次移动球时，记录操作的柱子编号（转换为1-based索引），作为最终输出的操作序列。

3. 终止条件

当分治范围缩小到 ( l+1 = r ) 时（即仅含一种颜色），该颜色的球已全部集中到对应柱子上，递归终止。

操作次数控制

• 分治策略将问题规模每次减半，每层递归的操作次数与柱子上的球数线性相关（( O(nm) ) 级别）。
• 总层数为 ( O(\log n) )，因此总操作次数为 ( O(nm \log n) )。对于 ( n \leq 50 )、( m \leq 400 ) 的数据，总操作次数远小于 ( 820000 )，满足题目限制。

代码实现解析

• 数据结构：用二维向量 a 存储每根柱子上的球（0-based索引，栈顶为向量末尾元素）。
• 分治递归：trav 函数通过递归划分颜色范围，调用 solve 函数处理局部柱子对。
• 移动操作：solve 函数中的 move 函数负责具体的球移动，并记录操作到 ans 中。
• 颜色判断：通过判断球的颜色是否属于当前划分的左半范围，决定移动方向。

示例说明（样例1）

• 输入：( n=2 )，( m=3 )，柱子0（1号柱）为 [0,0,1]（颜色1、1、2，0-based转换后），柱子1（2号柱）为 [1,0,1]（颜色2、1、2）。
• 分治第一步：范围 ([0, 2))，( mid=1 )，左半颜色为 ( <1 )（即0），右半颜色为 ( \geq1 )（即1）。
• 处理柱子0和1：通过 solve 函数移动球，将左半颜色（0）集中到柱子0，右半颜色（1）集中到柱子1，最终操作序列与样例一致。

#include <bits/stdc++.h>

#ifdef LOCAL
#include <debug.h>
#else
#define debug(...)
#define debug_arr(...)
#define debug_endl(...)
#endif

void solve() {
    int n, m;
    std::cin >> n >> m;

    std::vector<std::vector<int>> a(n + 1);

    for (int i = 0; i < n; i++) {
        a[i].resize(m);

        for (int j = 0; j < m; j++) {
            std::cin >> a[i][j];
            a[i][j]--;
        }
    }

    auto solve = [&](std::array<std::vector<bool>, 3> b) -> std::vector<std::pair<int, int>> {
        std::vector<std::pair<int, int>> res;

        auto move = [&](int i, int j) -> void {
            b[j].push_back(b[i].back());
            b[i].pop_back();
            res.emplace_back(i, j);
        };

        int c = std::ranges::count(b[0], false);

        while (c--) {
            move(1, 2);
        }

        while (!b[0].empty()) {
            move(0, b[0].back() + 1);
        }

        while (!b[1].empty()) {
            move(1, 0);
        }

        while (!b[2].empty() && b[2].back()) {
            move(2, 1);
        }

        while (!b[0].empty() && int(b[2 - b[0].back()].size()) < m) {
            move(0, 2 - b[0].back());
        }

        while (!b[2].empty()) {
            move(2, b[2].back());
        }

        return res;
    };

    std::vector<std::pair<int, int>> ans;

    auto trav = [&](auto &&self, int l, int r) -> void {
        if (l + 1 == r) {
            return;
        }

        int mid = std::midpoint(l, r);

        for (int i = l, j = mid; i < mid && j < r;) {
            if (std::ranges::count_if(a[i], [&](int x) -> bool {
            return x < mid;
        }) + std::ranges::count_if(a[j], [&](int x) -> bool {
            return x < mid;
        }) >= m) {
                std::array<std::vector<bool>, 3> b;
                int cnt = 0;

                for (int x : a[i]) {
                    b[1].push_back(x < mid && cnt++ < m);
                }

                for (int x : a[j]) {
                    b[0].push_back(x < mid && cnt++ < m);
                }

                for (auto [u, v] : solve(b)) {
                    u = std::array{j, i, n} [u], v = std::array{j, i, n} [v];
                    a[v].push_back(a[u].back());
                    a[u].pop_back();
                    ans.emplace_back(u, v);
                }

                i++;
            } else {
                std::array<std::vector<bool>, 3> b;
                int cnt = 0;

                for (int x : a[i]) {
                    b[0].push_back(x >= mid && cnt++ < m);
                }

                for (int x : a[j]) {
                    b[1].push_back(x >= mid && cnt++ < m);
                }

                for (auto [u, v] : solve(b)) {
                    u = std::array{i, j, n} [u], v = std::array{i, j, n} [v];
                    a[v].push_back(a[u].back());
                    a[u].pop_back();
                    ans.emplace_back(u, v);
                }

                j++;
            }
        }

        self(self, l, mid);
        self(self, mid, r);
    };

    trav(trav, 0, n);

    std::cout << ans.size() << "\n";

    for (auto [i, j] : ans) {
        std::cout << i + 1 << " " << j + 1 << "\n";
    }
}

int main() {
#ifndef LOCAL
    //freopen("ball.in", "r", stdin);
    //freopen("ball.out", "w", stdout);
#endif

    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.setf(std::ios::fixed);
    std::cout.precision(10);

    solve();

    return 0;
}