P9120 [春季测试 2023] 密码锁

题意

有一个 \(k\times n\) 的数组，你可以进行若干次以下的操作：

• 选择一列 \(i\in [1,n]\)，将该列 \(1,2,3,\cdots k\) 位置分别移动到 \(k,1,2,3\cdots,k-1\) 位置（转动一圈密码锁）；

最小化：

\[ \max_{j\in [1,k]}\Big\{\max_{i\in [1,n]}\{a_{i,j}\}-\max_{i\in [1,n]}\{a_{i,j}\}\Big\} \]

多测，\(\sum n\le 1.5\times 10^5,\ k\le 4\)

题解

首先注意到一个显然的事实：答案不会超过全局 \(\max\) 减全局 \(\min\)，这启发我们考虑全局 \(\max\) 和全局 \(\min\) 所在的位置。\(k=1\) 直接输出极差即可。\(k=2\) 我们将每列的较大值都放在全局最大值所在的一行，每列的较小值都放在全局最小值所在的另一行，一定不劣。

对于 \(k=3\)，先考虑二分答案，问题转化为判定极差能否小于等于 \(mid\)。注意到全局最大值 \(mx\) 所在的那行，所有数字都必须位于 \([mx-mid,mx]\) 中；全局最小值 \(mn\) 所在的那行，所有数字都必须位于 \([mn,mn+mid]\) 中。也就是说，当我们确定了 \(mx\) 和 \(mn\) 所在的行之后，只要每一列中待在这两行的数字都满足上述条件，那么这两行的限制就被满足了。

考虑如何处理另一行的限制。我们要求这一行的所有数字都必须同时包含于一个长度为 \(mid\) 的值域上的区间 \([t,t+mid]\)。如果我们只考虑一个数字对其他所有数字的约束，那么只能得到一个不充分的 \([x-mid,x+mid]\) 区间。我们注意到上面提到的 \(t\) 是很关键的，一个数字 \(x\) 限制了 \(t\) 必须位于 \([x-mid,x]\) 之间，而这显然是充要的。

因此，我们先枚举 \(mn\) 和 \(mx\) 所在的两行 \(r_1,r_2\)，然后依次考虑每一列在满足 \(r_1\) 和 \(r_2\) 的限制时，第三行可能填哪些数字。每一列对 \(t\) 的约束形如若干（\(\le 3\)）条线段的并，我们最后检查全部 \(n\) 列对 \(t\) 的约束是否有交即可。

对于 \(t=4\)，仍然先进行二分答案并枚举 \(r_1,r_2\)（\(mn,mx\) 所在的行），然后依次考虑每一列在满足这两行的限制下，另外两行（\(r_3,r_4\)）可能填的数字。由于我们需要满足两行内部的极差同时小于 \(mid\)，因此记 \(r_3\) 中所有数字都位于 \([t_1,t_1+mid]\)，\(r_4\) 中所有数字都位于 \([t_2,t_2+mid]\)。注意到某一列的一种方案对 \(t_1\) 和 \(t_2\) 的约束形如二维平面上的一个正方形 \(\big([x_1-mid,x_1],[x_2-mid,x_2]\big)\)，一列的所有合法方案（指满足 \(r_1,r_2\) 的限制）形如若干（\(\le 4\)）个正方形的并。

我们先对 \(\le 4\) 个正方形进行扫描线，将它们分解成若干无交的长方形；然后对所有长方形再进行扫描线，判断是否存在交集即可。

AC 代码

#include<bits/stl_algobase.h>
#include<ctype.h>
#include<cstdio>
#include<vector>
#include<algorithm>
#include<set>
#include<cassert>
using namespace std;
const int N = 5e4 + 10;
const int V = 3e4;
const int K = 4;
const int INF = 0x3f3f3f3f;

const char endl = '\n';

namespace io {
    struct istream {
        char ch;
        inline istream &operator>>(int &x) {
            while(!isdigit(ch = getchar()));
            x = ch - '0';
            while(isdigit(ch = getchar())) x = x * 10 + ch - '0';
            return *this;
        }
    } cin;
    struct ostream {
        char buf[60], top;
        inline ostream() : top(0) {}
        inline ostream &operator<<(char c) {
            putchar(c);
            return *this;
        }
        inline ostream &operator<<(const char s[]) {
            for(int i = 0; s[i]; i++) putchar(s[i]);
            return *this;
        }
        inline ostream &operator<<(int x) {
            if(x < 0) putchar('-'), x = -x;
            do buf[++top] = x % 10, x /= 10; while(x);
            while(top) putchar(buf[top--] + '0');
            return *this;
        }
    } cout;
}

using io::cin;
using io::cout;

int T, k;
int n;

int a[N][K + 3];

namespace simple {

    void work1() {
        int mn = INF, mx = 0;
        for(int i = 1; i <= n; i++) mn = min(mn, a[i][1]);
        for(int i = 1; i <= n; i++) mx = max(mx, a[i][1]);
        cout << mx - mn << '\n';
    }

    void work2() {
        int mn1 = INF, mn2 = INF, mx1 = 0, mx2 = 0;
        for(int i = 1; i <= n; i++) if(a[i][1] > a[i][2]) swap(a[i][1], a[i][2]);
        for(int i = 1; i <= n; i++) mn1 = min(mn1, a[i][1]);
        for(int i = 1; i <= n; i++) mx1 = max(mx1, a[i][1]);
        for(int i = 1; i <= n; i++) mn2 = min(mn2, a[i][2]);
        for(int i = 1; i <= n; i++) mx2 = max(mx2, a[i][2]);
        cout << max(mx1 - mn1, mx2 - mn2) << '\n';
    }

}

int mn, mx, ans;

namespace k3 {

    struct Op {
        int v, w, col;
        inline bool operator<(const Op &b) const {
            if(v != b.v) return v < b.v;
            return w < b.w;
        }
    };

    inline void rotate(int a[], int p) {
        if(p == 2) swap(a[1], a[2]), swap(a[2], a[3]);
        else if(p == 3) swap(a[2], a[3]), swap(a[1], a[2]);
    }

    int kp;
    int lock[5];
    int cnt[N], cc;
    vector<Op> op;

    void add_Line(int l, int r, int col) {
        op.push_back({l, 1, col});
        op.push_back({r + 1, -1, col});
    }

    bool check(int mid) {
        op.clear();
        for(int i = 1; i <= n; i++) {
            if(i <= 2 && lock[i]) {
                if(a[i][1] - mn > mid) return false;
                if(mx - a[i][5 - kp] > mid) return false;
                add_Line(a[i][kp] - mid, a[i][kp], i);
                continue;
            }
            for(int j = 1; j <= 3; j++, rotate(a[i], 3)) {
                if(a[i][1] - mn > mid) continue;
                if(mx - a[i][5 - kp] > mid) continue;
                add_Line(a[i][kp] - mid, a[i][kp], i);
            }
        }
        sort(op.begin(), op.end());
        bool flag = false;
        for(Op &o : op) {
            if(cnt[o.col] == 0 && o.w == 1) ++cc;
            if(cnt[o.col] == 1 && o.w == -1) --cc;
            cnt[o.col] += o.w;
            if(cc == n) flag = true;
        }
        return flag;
    }

    void calc() {
        int l = 0, r = V + 5;
        while(l < r) {
            int mid = (l + r) >> 1;
            if(check(mid)) r = mid;
            else l = mid + 1;
        }
        ans = min(ans, l);
    }

    void work3() {
        ans = INF;
        lock[1] = lock[2] = 0;
        mn = INF, mx = 0;
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= k; j++) {
                mn = min(mn, a[i][j]);
                mx = max(mx, a[i][j]);
            }
        }
        for(int i = 1; i <= n && a[1][1] != mn; i++) {
            for(int j = 1; j <= k; j++) {
                if(a[i][j] == mn) {
                    rotate(a[i], j);
                    swap(a[i], a[1]);
                    break;
                }
            }
        }
        if(a[1][2] == mx || a[1][3] == mx) {
            if(a[1][2] == mx) kp = 3;
            else kp = 2;
            lock[1] = 1;
            calc();
            cout << ans << '\n';
            return;
        }
        for(int i = 2; i <= n && a[2][1] != mx; i++) {
            for(int j = 1; j <= k; j++) {
                if(a[i][j] == mx) {
                    rotate(a[i], j);
                    swap(a[i], a[2]);
                    break;
                }
            }
        }
        lock[1] = lock[2] = 1;
        rotate(a[2], 3);
        kp = 3;
        calc();
        rotate(a[2], 3);
        kp = 2;
        calc();
        cout << ans << '\n';
    }

}

namespace k4 {

    namespace SegT {
        int mx[4 * V], tag[4 * V];
        inline int lc(int x) { return x << 1; }
        inline int rc(int x) { return x << 1 | 1; }
        inline void push_up(int p) { mx[p] = max(mx[lc(p)], mx[rc(p)]); }
        inline void move_tag(int p, int tg) {
            mx[p] += tg;
            tag[p] += tg;
        }
        void push_down(int p) {
            if(!tag[p]) return;
            move_tag(lc(p), tag[p]);
            move_tag(rc(p), tag[p]);
            tag[p] = 0;
        }
        void add(int p, int l, int r, int ql, int qr, int v) {
            if(ql <= l && r <= qr) { move_tag(p, v); return; }
            push_down(p);
            int mid = (l + r) >> 1;
            if(ql <= mid) add(lc(p), l, mid, ql, qr, v);
            if(mid < qr) add(rc(p), mid + 1, r, ql, qr, v);
            push_up(p);
        }
        int query() { return mx[1]; }
    }

    inline void rotate(int a[], int p) {
        if(p == 1) return;
        if(p == 2) swap(a[1], a[2]), swap(a[2], a[3]), swap(a[3], a[4]);
        else if(p == 3) swap(a[1], a[3]), swap(a[2], a[4]);
        else swap(a[3], a[4]), swap(a[2], a[3]), swap(a[1], a[2]);
    }

    struct Op3 {
        int x, w;
        inline bool operator<(const Op3 &b) const {
            if(x != b.x) return x < b.x;
            return w < b.w;
        }
    };

    struct Op4 {
        int x, y1, y2, w;
        inline bool operator<(const Op4 &b) const {
            if(x != b.x) return x < b.x;
            return w < b.w;
        }
    };

    multiset<Op3> op3;
    vector<Op4> op34, op4;

    void add_Rec(int x, int y, int d) {
        op34.push_back({max(1, x - d), max(1, y - d), y, 1});
        op34.push_back({x + 1, max(1, y - d), y, -1});
    }

    void enter() {
        sort(op34.begin(), op34.end());
        int prex = -1;
        for(Op4 &o : op34) {
            if(~prex && o.x > prex) {
                int cnt = 0, prey;
                for(const Op3 &o2 : op3) {
                    if(o2.w == 1 && cnt == 0) prey = o2.x;
                    if(o2.w == -1 && cnt == 1) {
                        op4.push_back({prex, prey, o2.x - 1, 1});
                        op4.push_back({o.x, prey, o2.x - 1, -1});
                    }
                    cnt += o2.w;
                }
            }
            prex = o.x;
            if(o.w == 1) {
                op3.insert({o.y1, 1});
                op3.insert({o.y2 + 1, -1});
            } else {
                op3.erase(op3.find({o.y1, 1}));
                op3.erase(op3.find({o.y2 + 1, -1}));
            }
        }
        if(!op3.empty()) throw;
        op34.clear();
    }

    int lock[5];
    int mxp, ans;

    bool check(int mid) {
        op4.clear();
        for(int i = 1; i <= n; i++) {
            if(i <= 2 && lock[i]) {
                if(a[i][1] - mn > mid) return false;
                if(mx - a[i][mxp] > mid) return false;
                if(mxp == 2) add_Rec(a[i][3], a[i][4], mid);
                else if(mxp == 3) add_Rec(a[i][2], a[i][4], mid);
                else add_Rec(a[i][2], a[i][3], mid);
                enter();
                continue;
            }
            for(int j = 1; j <= 4; j++, rotate(a[i], 4)) {
                if(a[i][1] - mn > mid) continue;
                if(mx - a[i][mxp] > mid) continue;
                if(mxp == 2) add_Rec(a[i][3], a[i][4], mid);
                else if(mxp == 3) add_Rec(a[i][2], a[i][4], mid);
                else add_Rec(a[i][2], a[i][3], mid);
            }
            enter();
        }
        sort(op4.begin(), op4.end());
        bool flag = false;
        for(Op4 &o : op4) {
            SegT::add(1, 1, V, o.y1, o.y2, o.w);
            if(SegT::query() >= n) flag = true;
        }
        return flag;
    }

    void calc() {
        op4.clear();
        int l = 0, r = V + 5;
        while(l < r) {
            int mid = (l + r) >> 1;
            if(check(mid)) r = mid;
            else l = mid + 1;
        }
        ans = min(ans, l);
    }

    void work4() {
        ans = INF;
        mn = INF, mx = 0;
        lock[1] = lock[2] = 0;
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= k; j++) {
                mn = min(mn, a[i][j]);
                mx = max(mx, a[i][j]);
            }
        }
        for(int i = 1; i <= n && a[1][1] != mn; i++) {
            for(int j = 1; j <= k; j++) {
                if(a[i][j] == mn) {
                    rotate(a[i], j);
                    swap(a[1], a[i]);
                    break;
                }
            }
        }
        if(a[1][2] == mx || a[1][3] == mx || a[1][4] == mx) {
            if(a[1][2] == mx) mxp = 2;
            else if(a[1][3] == mx) mxp = 3;
            else mxp = 4;
            lock[1] = 1;
            calc();
            cout << ans << '\n';
            return;
        }
        for(int i = 2; i <= n; i++) {
            for(int j = 1; j <= k; j++) {
                if(a[i][j] == mx) {
                    rotate(a[i], j);
                    swap(a[2], a[i]);
                    break;
                }
            }
        }
        lock[1] = lock[2] = 1;
        rotate(a[2], 4);
        mxp = 2;
        calc();
        rotate(a[2], 4);
        mxp = 3;
        calc();
        rotate(a[2], 4);
        mxp = 4;
        calc();
        cout << ans << '\n';
    }

}

using simple::work1;
using simple::work2;
using k3::work3;
using k4::work4;

int main() {

    cin >> T >> k;
    while(T--) {
        cin >> n;
        for(int j = 1; j <= k; j++) {
            for(int i = 1; i <= n; i++) {
                cin >> a[i][j];
            }
        }
        if(k == 1) work1();
        else if(k == 2) work2();
        else if(k == 3) work3();
        else if(k == 4) work4();
    }

    return 0;
}