[春季测试 2023] 密码锁

upd: 被指出 $k=3$ 的写法有问题，已经换上了新写法。

$k=1,2$ 的思路非常简单。

我们考虑 $k=3$，首先显然可以二分答案，然后在 $k=2$ 的时候，我们提到了 $\max,\min$，我们考虑扩展一下思路。首先显然全局最大值和最小值在同一行中的情况一定是不优的。所以我们来枚举它们分别在哪两行。注意，这里有可能会出现一些奇怪的情况，比如极值不止一个，或者因为全局最大值和最小值在同一列导致无法达成目标。不过因为我们这样放，只是假设某两行的极值是给定值，而这个假设值比事实上的值带来的限制一定不会更松。所以只要能在这样的限制下找到解，一定是合法的，并且由于最终解中一定可以存在在不同行的 $\max,\min$，所以我们也不会遗漏情况。

然后说完这些东西剩下的就很简单了。考虑二分的值确定了这两行数的范围，从而每一列能在不确定的第三行放哪个数也是可以确定的。然后问题就转化为了，有 $n$ 个数，每个数可以有不超过 $3$ 种的选择，问极差能不能不超过某个数。这当然可以用卡牌游戏做，不过有一个更具有扩展性的做法。

考虑对于每个数 $x$，它对于 $\min$ 的限制是 $[x-k,x]$，其中 $k$ 是我们二分的极差。然后我们对于每一列可能的数，我们把它对应的限制求并后加入统计。看看是否存在一个点被 $n$ 个限制同时覆盖即可。线段求并只需按照 $l$ 排序后扫一遍，覆盖次数可以用线段树求解。时间复杂度 $\mathcal{O}(kn\log^2 a)$。

然后我们来看看 $k=4$ 的情况。钦定完 $\max,\min$ 后思路是类似的，只不过这次我们对于 $\min$ 的限制变成了 $2$ 维的。模仿上面的思路，我们需要矩阵并和在矩阵并后的图形上整体 $+1$。因为矩阵并之后不像线段依然能保持一个好维护的形状，所以我们考虑把并后的图形拆成若干矩形，然后再用扫描线维护矩形加。这个拆我们可以考虑容斥。考虑矩阵集合的一个子集 $S$，我们求出这个集合的交，如果 $|S|$ 为奇数，就矩阵 $+1$，否则就 $-1$，原因显然。如果你还不太理解可以看看这幅图：

蓝色，绿色，黄色矩形直接加，然后红色矩形减，即可。然后就做完了。时间复杂度 $\mathcal{O}(k2^kn\log^2 a)$。

我们来考虑其他常数更小的做法。发现在扫描线矩阵求并的过程中，我们要做的事情是对于若干高度一样的矩阵求并。本质上就是线段求并，这启发我们抛弃容斥，用类似扫描线的思路来做这个东西。

考虑把所有端点都离散化，然后离散化后相邻的两个位置，它们之间的矩形结构是相同的，可以一起处理。（还有一种理解思路就是 $k=3$ 的情况长高了）找到应该加的矩形后，后面就一模一样了，具体实现可以见代码，或者可以看看这幅图：

我们分别把绿色红色蓝色黄色一条条加进去即可。

代码中是把 $x,y$ 坐标一起离散化，这样单次 work4 的线段树修改次数是 $4nk$ 的，如果 $x,y$ 分别离散化可以做到 $2nk$，但我懒得写了。时间复杂度 $\mathcal{O}(nk\log^2a)$。

#include <cstdio>
#include <vector>
#include <cassert>
#include <algorithm>
const int N = 1e5 + 10; int a[5][N]; 
std::vector<int> v3[N]; int d[N], mx, mn;
struct IO
{
    static const int N = 1 << 22;
    char buf[N], pbuf[N], *p1 = buf, *p2 = buf, *pp = pbuf;
    #define gc() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, N, stdin), p1 == p2) ? EOF : *p1++)  
    template <typename T>
    void read(T& x)
    {
        x = 0; char ch; int f = 0;
        while ((ch = gc()) < '0' || ch > '9') f |= (ch == '-');
        while (x = (x << 1) + (x << 3) + (ch ^ 48), (ch = gc()) >= '0' && ch <= '9') ;
        if (f) x = ~x + 1;
    }
    void putc(char c)
    {
        if (pp - pbuf == N) fwrite(pbuf, 1, N, stdout), pp = pbuf;
        *pp++ = c;
    }
    void puts(const char* s) { while (*s) putc(*s), ++s; putc('\n'); }
    template <typename T>
    void print(T x)
    {
        static int st[20]; int tp = 0;
        if (x < 0) putc('-'), x = ~x + 1;
        do st[++tp] = x % 10, x /= 10; while (x);
        while (tp) putc(st[tp--] + '0');
    }
    ~IO() { fwrite(pbuf, pp - pbuf, 1, stdout); }
}io;
struct SegTree
{
    #define ls(k) (k << 1)
    #define rs(k) (k << 1 | 1)
    struct node{ int mx, tag, clr; }h[N << 2];
    void pushup(int k) { h[k].mx = std::max(h[ls(k)].mx, h[rs(k)].mx); }
    void add(int k, int v) { h[k].mx += v; h[k].tag += v; }
    void clr(int k) { h[k].clr = 1; h[k].mx = h[k].tag = 0; }
    void pushdown(int k)
    {
        if (h[k].clr) clr(ls(k)), clr(rs(k)), h[k].clr = 0;
        if (h[k].tag) add(ls(k), h[k].tag), add(rs(k), h[k].tag), h[k].tag = 0;
    }
    void change(int k, int l, int r, int x, int y, int v)
    {
        if (x <= l && r <= y) return add(k, v);
        int mid = (l + r) >> 1; pushdown(k);
        if (x <= mid) change(ls(k), l, mid, x, y, v);
        if (mid < y) change(rs(k), mid + 1, r, x, y, v);
        pushup(k);
    }
    #undef ls
    #undef rs
}sgt;
bool work3(int n, int k)
{
   	sgt.clr(1);
    for (int i = 1; i <= n; ++i)
    {
        std::pair<int, int> seg[3];
        for (int j = 0; j < (int)v3[i].size(); ++j)
            seg[j].first = std::max(mn, v3[i][j] - k), seg[j].second = v3[i][j];
        std::sort(seg, seg + v3[i].size());
		sgt.change(1, mn, mx, seg[0].first, seg[0].second, 1);
        ++d[seg[0].first]; --d[seg[0].second + 1];
        for (int j = 1; j < (int)v3[i].size(); ++j) 
        {
            if (seg[j].first > seg[j - 1].second)
				sgt.change(1, mn, mx, seg[j].first, seg[j].second, 1);
            else if (seg[j - 1].second + 1 <= seg[j].second)
				sgt.change(1, mn, mx, seg[j - 1].second + 1, seg[j].second, 1);
        }
    }
	return (sgt.h[1].mx == n);
}
bool check3(int n, int l, int r, int k)
{
    bool flg = 1; for (int i = 1; i <= n; ++i) v3[i].clear();
    for (int i = 1; i <= n; ++i)
    {
        if (a[1][i] >= l && a[2][i] <= r) v3[i].push_back(a[3][i]);
        if (a[2][i] >= l && a[3][i] <= r) v3[i].push_back(a[1][i]);
        if (a[3][i] >= l && a[1][i] <= r) v3[i].push_back(a[2][i]);
        if (v3[i].empty()) { flg = 0; break; }
    }
    if (flg && work3(n, k)) return true;
    flg = 1; for (int i = 1; i <= n; ++i) v3[i].clear();
    for (int i = 1; i <= n; ++i)
    {
        if (a[1][i] >= l && a[3][i] <= r) v3[i].push_back(a[2][i]);
        if (a[2][i] >= l && a[1][i] <= r) v3[i].push_back(a[3][i]);
        if (a[3][i] >= l && a[2][i] <= r) v3[i].push_back(a[1][i]);
        if (v3[i].empty()) { flg = 0; break; }
    }
    if (flg && work3(n, k)) return true;
    return false;
}
std::vector<std::pair<int, int>> vec[N]; std::pair<int, int> v4[N][4]; int siz[N];
int bkt[N * 16], tp, t[20], cnt; 
std::vector<std::pair<int, int>> ad[20], dl[20];
bool work4(int n, int k)
{
    tp = 0; int flg = 0;
    for (int i = 1; i <= n; ++i)
    {
        cnt = 0;
        for (int j = 0; j < siz[i]; ++j)
        {
            t[++cnt] = std::max(v4[i][j].first - k, mn);
            t[++cnt] = std::max(v4[i][j].second - k, mn);
            t[++cnt] = v4[i][j].first + 1; 
            t[++cnt] = v4[i][j].second + 1;
        }
        std::sort(t + 1, t + cnt + 1); cnt = std::unique(t + 1, t + cnt + 1) - t - 1;
        for (int j = 1; j <= cnt; ++j) ad[j].clear(), dl[j].clear();
        for (int j = 0; j < siz[i]; ++j)
        {
            int lef = std::lower_bound(t + 1, t + cnt + 1, std::max(v4[i][j].first - k, mn)) - t,
                dw = std::lower_bound(t + 1, t + cnt + 1, std::max(v4[i][j].second - k, mn)) - t,
                rig = std::lower_bound(t + 1, t + cnt + 1, v4[i][j].first + 1) - t,
                up = std::lower_bound(t + 1, t + cnt + 1, v4[i][j].second + 1) - t;
            ad[dw].emplace_back(lef, rig);
            dl[up].emplace_back(lef, rig);
        }
        for (int j = 1; j <= cnt; ++j) d[j] = 0, bkt[++tp] = t[j];
        for (int j = 1; j <= cnt; ++j)
        {
            int sum = 0, las = -1;
            for (auto p : ad[j]) ++d[p.first], --d[p.second];
            for (auto p : dl[j]) --d[p.first], ++d[p.second];
            for (int k = 1; k <= cnt; ++k)
            {
                sum += d[k];
                if (!sum)
                {
                    if (las == -1) continue;
                    vec[t[j]].emplace_back(t[las], 1);
                    vec[t[j]].emplace_back(t[k], -1);
                    vec[t[j + 1]].emplace_back(t[las], -1);
                    vec[t[j + 1]].emplace_back(t[k], 1);
                    las = -1;
                } else if (las == -1) las = k;
            }
        }
    }
    std::sort(bkt + 1, bkt + tp + 1);
    tp = std::unique(bkt + 1, bkt + tp + 1) - bkt - 1;
    for (int i = 1; i <= tp; ++i)
    {
        vec[bkt[i]].emplace_back(mn, 0);
        vec[bkt[i]].emplace_back(mx + 1, 0);
    }
    sgt.clr(1);
    for(int i = 1; i <= tp; ++i)
    {
        auto& v = vec[bkt[i]];
        std::sort(v.begin(), v.end()); int sum = v[0].second;
        for (int j = 1; j < (int)v.size(); ++j)
        {
            if (v[j - 1].first < v[j].first && sum)
                sgt.change(1, mn, mx, v[j - 1].first, v[j].first - 1, sum);
            sum += v[j].second;
        }
        if (sgt.h[1].mx == n) { flg = 1; break; }
    }
    for (int i = 1; i <= tp; ++i) vec[bkt[i]].clear();
    return flg;
}
bool check4(int n, int l, int r, int k)
{
    bool flg = 1; 
    for (int i = 1; i <= n; ++i)
    {
        siz[i] = 0;
        if (a[1][i] >= l && a[2][i] <= r) v4[i][siz[i]++] = std::make_pair(a[3][i], a[4][i]);
        if (a[2][i] >= l && a[3][i] <= r) v4[i][siz[i]++] = std::make_pair(a[4][i], a[1][i]);
        if (a[3][i] >= l && a[4][i] <= r) v4[i][siz[i]++] = std::make_pair(a[1][i], a[2][i]);
        if (a[4][i] >= l && a[1][i] <= r) v4[i][siz[i]++] = std::make_pair(a[2][i], a[3][i]);
        if (!siz[i]) { flg = 0; break; }
    }
    if (flg && work4(n, k)) return true;
    flg = 1;
    for (int i = 1; i <= n; ++i)
    {
        siz[i] = 0;
        if (a[1][i] >= l && a[3][i] <= r) v4[i][siz[i]++] = std::make_pair(a[4][i], a[2][i]);
        if (a[2][i] >= l && a[4][i] <= r) v4[i][siz[i]++] = std::make_pair(a[1][i], a[3][i]);
        if (a[3][i] >= l && a[1][i] <= r) v4[i][siz[i]++] = std::make_pair(a[2][i], a[4][i]);
        if (a[4][i] >= l && a[2][i] <= r) v4[i][siz[i]++] = std::make_pair(a[3][i], a[1][i]);
        if (!siz[i]) { flg = 0; break; }
    }
    if (flg && work4(n, k)) return true;
    flg = 1;
    for (int i = 1; i <= n; ++i)
    {
        siz[i] = 0;
        if (a[1][i] >= l && a[4][i] <= r) v4[i][siz[i]++] = std::make_pair(a[2][i], a[3][i]);
        if (a[2][i] >= l && a[1][i] <= r) v4[i][siz[i]++] = std::make_pair(a[3][i], a[4][i]);
        if (a[3][i] >= l && a[2][i] <= r) v4[i][siz[i]++] = std::make_pair(a[4][i], a[1][i]);
        if (a[4][i] >= l && a[3][i] <= r) v4[i][siz[i]++] = std::make_pair(a[1][i], a[2][i]);
        if (!siz[i]) { flg = 0; break; }
    }
    if (flg && work4(n, k)) return true;
    return false;
}
int main()
{ 
    int qwq, k; io.read(qwq); io.read(k);
    while (qwq--)
    {
        int n; mx = 0, mn = 2e9; io.read(n);
        for (int i = 1; i <= k; ++i)
            for (int j = 1; j <= n; ++j) 
                io.read(a[i][j]), mx = std::max(mx, a[i][j]), mn = std::min(mn, a[i][j]);
        if (k == 1) io.print(mx - mn);
        else if (k == 2)
        {
            for (int i = 1; i <= n; ++i)
                if (a[1][i] < a[2][i]) std::swap(a[1][i], a[2][i]);
            int ans = 0;
            for (int i = 1; i <= 2; ++i)
            {
                int mx = 0, mn = 2e9;
                for (int j = 1; j <= n; ++j)
                    mx = std::max(mx, a[i][j]), mn = std::min(mn, a[i][j]);
                ans = std::max(ans, mx - mn);
            }
            io.print(ans);
        }
        else if (k == 3)
        {
            int l = 0, r = mx - mn, mid, ans = -1;
            while (l <= r)
            {
                mid = (l + r) >> 1;
                if (check3(n, mx - mid, mn + mid, mid)) ans = mid, r = mid - 1;
                else l = mid + 1;
            }
            io.print(ans);
        }
        else if (k == 4)
        {
            int l = 0, r = mx - mn, mid, ans = -1;
            while (l <= r)
            {
                mid = (l + r) >> 1;
                if (check4(n, mx - mid, mn + mid, mid)) ans = mid, r = mid - 1;
                else l = mid + 1;
            }
            io.print(ans);
        }
        io.puts("");
    }
    return 0;
}