代码：
```cpp
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#define x first
#define y second
#define mp make_pair
using namespace std;
typedef pair<int,int> PII;
const int N = 5e4 + 10, K = 4, INF = 0x3f3f3f3f, mod4[8] = {0, 1, 2, 3, 0, 1, 2, 3}, mod3[6] = {0, 1, 2, 0, 1, 2};
int a[K][N], n, k, mn, mx, b[N << 4], tot;
vector <PII> G, op;
struct SegmentTree{
int l, r, add, mx;
#define l(x) tr[x].l
#define r(x) tr[x].r
#define lc(x) x << 1
#define rc(x) x << 1 | 1
#define add(x) tr[x].add
#define mx(x) tr[x].mx
}tr[N << 6];
struct node{
int x, y1, y2, z;
bool operator < (const node& t) const
{
if(x == t.x) return z < t.z;
return x < t.x;
}
}opt[N << 4];
struct Square{
int a, b, c, d;
}sq[N << 2];
vector <node> last;
void pushup(int p)
{
mx(p) = max(mx(lc(p)), mx(rc(p))) + add(p);
}
void pushadd(int p, int add)
{
add(p) += add, mx(p) += add;
}
void build(int p, int l, int r)
{
tr[p] = SegmentTree({l, r, 0, 0});
if(l == r) return;
int mid = l + r >> 1;
build(lc(p), l, mid), build(rc(p), mid + 1, r);
}
void change(int p, int x, int d)
{
if(l(p) == r(p))
{
pushadd(p, d);
return;
}
int mid = l(p) + r(p) >> 1;
if(x <= mid)
{
change(lc(p), x, d);
}
else
{
pushadd(lc(p), d);
change(rc(p), x, d);
}
pushup(p);
}
int solve1() {return mx - mn;}
int solve2()
{
int res = 0;
for(int i = 1; i <= n; i++)
{
if(a[0][i] > a[1][i]) swap(a[0][i], a[1][i]);
}
for(int i = 0; i < k; i++)
{
int mx = 0, mn = INF;
for(int j = 1; j <= n; j++)
{
mx = max(mx, a[i][j]), mn = min(mn, a[i][j]);
}
res = max(res, mx - mn);
}
return res;
}
int val(int x)
{
return lower_bound(b + 1, b + tot + 1, x) - b;
}
void get()
{
sort(G.begin(), G.end());
if(!G.empty())
{
PII now = G[0];
for(int u = 1; u < G.size(); u++)
{
PII p = G[u];
if(now.y >= p.x)
{
now.y = p.y;
}
else
{
op.push_back(now);
now = p;
}
}
op.push_back(now);
}
}
bool valid3(int mid)
{
int posmn = 0;
for(int posmx = 1; posmx < k; posmx++)
{
int pos = 3 - posmn - posmx;
tot = 0, op.clear();
for(int i = 1; i <= n; i++)
{
G.clear();
for(int j = 0; j < k; j++)
{
if(a[mod3[posmn + j]][i] <= mn + mid && a[mod3[posmx + j]][i] >= mx - mid)
{
G.push_back(mp(max(mn, a[mod3[pos + j]][i] - mid), a[mod3[pos + j]][i]));
}
}
get();
}
if(!op.size())
{
continue;
}
for(int i = 0; i < op.size(); i++)
{
int x = op[i].x, y = op[i].y;
b[++tot] = x, b[++tot] = y;
}
sort(b + 1, b + tot + 1);
tot = unique(b + 1, b + tot + 1) - b - 1;
build(1, 1, tot);
for(int i = 0; i < op.size(); i++)
{
int x = val(op[i].x), y = val(op[i].y);
if(x > 1) change(1, x - 1, -1);
change(1, y, 1);
}
if(tr[1].mx == n) return 1;
}
return 0;
}
int solve3()
{
int l = 0, r = mx;
while(l < r)
{
int mid = l + r >> 1;
if(valid3(mid)) r = mid;
else l = mid + 1;
}
return l;
}
bool valid4(int mid)
{
int posmn = 0;
for(int posmx = 1; posmx < k; posmx++)
{
int pos1, pos2, cntopt = 0;
for(int i = 0; i < k; i++)
{
if(i != posmn && i != posmx)
{
pos1 = i, pos2 = 6 - posmn - posmx - pos1;
break;
}
}
for(int i = 1; i <= n; i++)
{
int cntsq = tot = 0;
for(int j = 0; j < k; j++)
{
if(a[mod4[posmn + j]][i] <= mn + mid && a[mod4[posmx + j]][i] >= mx - mid)
{
b[++tot] = a[mod4[pos1 + j]][i] - mid;
b[++tot] = a[mod4[pos1 + j]][i] + 1;
sq[++cntsq] = Square({a[mod4[pos1 + j]][i] - mid, a[mod4[pos2 + j]][i] - mid, a[mod4[pos1 + j]][i], a[mod4[pos2 + j]][i]});
}
}
sort(b + 1, b + tot + 1);
tot = unique(b + 1, b + tot + 1) - b - 1;
last.clear();
for(int r = 1; r <= tot; r++)
{
G.clear(), op.clear();
int x = b[r];
for(int u = 0; u < last.size(); u++)
{
node p = last[u];
opt[++cntopt] = {x, p.y1, p.y2, -1};
}
for(int t = 1; t <= cntsq; t++)
{
if(sq[t].a <= x && sq[t].c >= x)
{
G.push_back(mp(sq[t].b, sq[t].d));
}
}
get();
last.clear();
for(int u = 0; u < op.size(); u++)
{
opt[++cntopt] = {x, op[u].x, op[u].y, 1};
last.push_back(opt[cntopt]);
}
}
}
sort(opt + 1, opt + cntopt + 1);
tot = 0;
for(int i = 1; i <= cntopt; i++)
{
b[++tot] = opt[i].y1, b[++tot] = opt[i].y2;
}
sort(b + 1, b + tot + 1);
tot = unique(b + 1, b + tot + 1) - b - 1;
if(!tot) continue;
build(1, 1, tot);
for(int i = 1; i <= cntopt; i++)
{
opt[i].y1 = val(opt[i].y1), opt[i].y2 = val(opt[i].y2);
if(opt[i].y1 > 1) change(1, opt[i].y1 - 1, -opt[i].z);
change(1, opt[i].y2, opt[i].z);
if(tr[1].mx == n)
{
return 1;
}
}
}
return 0;
}
int solve4()
{
int l = 0, r = mx;
while(l < r)
{
int mid = r - l > 200 ? (l + r >> 1) : ((l + 3 * r) >> 2);
if(valid4(mid)) r = mid;
else l = mid + 1;
}
return l;
}
int main()
{
//freopen("data.in.txt", "r", stdin);
int T;
scanf("%d%d", &T, &k);
while(T--)
{
mx = 0, mn = INF;
scanf("%d", &n);
for(int i = 0; i < k; i++)
{
for(int j = 1; j <= n; j++)
{
scanf("%d", &a[i][j]);
mx = max(mx, a[i][j]), mn = min(mn, a[i][j]);
}
}
//if(T) continue;
if(k == 1) printf("%d\n", solve1());
else if(k == 2) printf("%d\n", solve2());
else if(k == 3) printf("%d\n", solve3());
else printf("%d\n", solve4());
}
//printf("%d %d\n", totall, cgall);
return 0;
}
```
by goodier @ 2023-04-16 10:31:29
复杂度大概是$O(nk^3 log(nk) loga)$
by goodier @ 2023-04-16 10:35:09
请问是我的复杂度错了吗？谢谢各位大佬
by goodier @ 2023-04-16 10:37:02
建议你去看题解。
by shooting__star @ 2023-04-16 11:00:16
@[goodier](/user/242039) 这个复杂度可以过，我就是这么写的，但是要大力卡常
by _ChiFAN_ @ 2023-06-19 15:40:03