题解：CF2059E2 Stop Gaming (Hard Version)

· · 题解

为什么没有人提到线性做法？

把输入矩阵拍平成序列，序列被划分为 n 个长为 m 的段。操作相当于在某一个段头插入一个元素。

显然 a 中最后留下的元素是一个前缀。问题可以转化为在 b 中选择匹配 a 的一个前缀的最长子序列。

但注意到不是所有匹配 a 的子序列都是合法的，考虑一个未被选中到子序列的元素 i，则 i 一定是某一个段头在某一个时刻插入的元素，记 i 到前面最近的段头的距离是 d_i，又记 [1,i-1] 中未选中的元素（即插入的元素）有 k_i 个，如果 d_i>k_i，由于 >i 的元素不会影响 i 元素的排名，而 i 在最近的段头插入后，根本没有足够多的元素能够将它“挤”到当前位置，这就一定不合法，反之只需要在 <i 的元素恰好还剩 d_i 个没有插入的时候在最近的段头立即插入 i 就合法了。

因此序列合法当且仅当所有 i 满足 d_i \le k_i。

考虑贪心，从前往后贪心匹配，记录 lim 表示当前的 k_i，能匹配就直接匹配，如果无法匹配分讨两种情况：如果当前位置 d_i \le lim，此时当前元素可以不选，所以直接跳过，并将 lim+1。反之当前元素不满足不选的条件，我们只能让匹配了的一些元素不选，使得 lim 足够大。注意到我们需要回退 K=d_i - lim 个元素，而匹配的后 K 个元素一定构成 [i-K,i-1] 的连续段（证明大体就是如果不构成连续段则 lim 会增大），所以直接回退后 K 个元素就是最优秀的。

考虑如何输出方案，由于已经确定了哪些数是位于子序列中，k_i,d_i 均固定。现在只需要下标从小到大扫描线，每次将一个未选中元素 i 插入到操作序列的倒数第 d_i 个位置就行了。

由于 d_i \le m，而对于同一段的未确定元素 d_i 单调递增，使用链表维护操作序列，同一段可以做到均摊 O(m) 的复杂度，一共只有 n 段，总复杂度 O(nm)。

#include<bits/stdc++.h>
using ll = long long; using ull = unsigned long long; using uint = unsigned int;
#define ld std::cin
#define jyt std::cout
#define cmd std::cerr
#define REQ(i, l, r) for (int i = l; i <  r; ++i)
#define REP(i, l, r) for (int i = l; i <= r; ++i)
#define PER(i, l, r) for (int i = l; i >= r; --i) 
const int MAXL = 1 << 20; char buf[MAXL], *buf1 = buf, *buf2 = buf;
#define gc() (buf1 == buf2 && (buf2 = (buf1 = buf) + fread(buf, 1, MAXL, stdin), buf1 == buf2) ? EOF : *buf1++)
inline ll ldr() {
    ll x = 0; bool f = 0; char ch = gc();
    while (ch < '0' || '9' < ch) f = (ch == '-'), ch = gc();
    while ('0' <= ch && ch <= '9') x = x * 10 + (ll)(ch - '0'), ch = gc();
    return (f ? -x : +x);
}
inline int ldc() { char ch = gc(); while (ch < 'a' || 'z' < ch) ch = gc(); return ch - 'a'; }
inline int ldn() { char ch = gc(); while (ch < '0' || '9' < ch) ch = gc(); return ch - '0'; }
#define mset(a, v, n) memset((a), (v), sizeof((a)[0]) * (n))
std::mt19937_64 R64(std::chrono::steady_clock::now().time_since_epoch().count());
const int N = 3e5 + 3; 
int H, W, n, a[N], b[N]; 
bool mark[N]; std::list<std::pair<int, int> > S;
inline signed Create() {
    H = ldr(), W = ldr(), n = H * W;
    REP(i, 1, n) a[i] = ldr();
    REP(i, 1, n) b[i] = ldr();
    int lim = 1, pt = 1;
    REP(i, 1, n) {
        if (a[pt] == b[i]) { ++pt; continue; }
        int _ = std::max(0, (i - 1) % W + 1 - lim);
        REQ(k, i - _, i) mark[k] = 1;
        pt -= _, lim += _, mark[i] = 1, ++lim;
    }
    jyt << n - (pt - 1) << '\n';
    auto it = S.begin(); int rk = 0;
    REP(i, 1, n) if (mark[i]) {
        int _ = (i - 1) % W, f = (i - 1) / W + 1;
        if (rk > _) it = S.begin(), rk = 0;
        while (rk < _) ++it, ++rk;
        it = S.insert(it, std::make_pair(f, b[i]));
    }
    std::reverse(S.begin(), S.end());
    for (auto node : S) jyt << node.first << ' ' << node.second << '\n';
    return 0;
}
inline void FlyWheel() { S.clear(); REP(i, 1, n) mark[i] = 0; }
signed main() {
    std::ios::sync_with_stdio(false), ld.tie(0), jyt.tie(0);
    int TEST = ldr();
    while (TEST--) Create(), FlyWheel();
    return 0;
}