思路

• 关键等价：整场比赛中被击败的战力序列必须严格递增（若上一次击败的是 $v$，则新战力为 $v+1$，下一次需选 $\ge v+1$ 的对手，等价于严格变大）。
• 同一层内可以任意选择对手并自由排序；跨层只能按层号递增的顺序进行。于是可以将每一层的数组升序排序后按层连接成序列 $S$。
• 问题化为：$S$ 的严格上升子序列（LIS）最大长度。初始战力为 $1$ 仅要求第一项 $\ge 1$，对任意 $a_{i,j}\ge 1$ 总是满足，因此不额外限制。
• 计算方法：对每层排序升序后拼接；对拼接序列做严格 LIS（“牌堆法”）：维护数组 $tails$，对每个值 $x$ 用二分下界（$lower_bound$）找到第一个 $\ge x$ 的位置替换；未找到则追加。最终答案为 $|tails|$。

正确性说明

• 任一可行操作序列对应一个严格递增的被击败战力序列，反之，任一严格递增序列都可通过在各层内按升序挑选实现（层序不可逆，恰与拼接顺序一致）。
• 将每层排序不会减少可取得的 LIS 长度：任一严格递增的选取在该层内本就按值递增，排序只会保留或放宽它的相对次序。
• 因而答案即为拼接序列 $S$ 的严格 LIS 长度。

复杂度

• 排序总复杂度：$\sum O(m_i \log m_i)$；LIS：$O(Mlog M)$，其中 $M=\sum m_i \le 2\times 10^5$。总空间 $O(M)$。

C++ 实现

#include <bits/stdc++.h>
using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n;
	if (!(cin >> n)) return 0;
	vector<int> seq;
	seq.reserve(200000);
	for (int i = 0; i < n; ++i) {
		int m; cin >> m;
		vector<int> a(m);
		for (int j = 0; j < m; ++j) cin >> a[j];
		// 每层内部升序排序
		sort(a.begin(), a.end());
		// 按层拼接
		for (int x : a) seq.push_back(x);
	}
	// 严格上升子序列长度（牌堆法 + lower_bound）
	vector<int> tails;
	tails.reserve(seq.size());
	for (int x : seq) {
		auto it = lower_bound(tails.begin(), tails.end(), x);
		if (it == tails.end()) tails.push_back(x);
		else *it = x;
	}
	cout << (int)tails.size() << '\n';
	return 0;
}

Python

import sys
from bisect import bisect_left

def main():
	data = list(map(int, sys.stdin.buffer.read().split()))
	it = iter(data)
	n = next(it, None)
	if n is None:
		return
	seq = []
	for _ in range(n):
		m = next(it)
		arr = [next(it) for _ in range(m)]
		# 每层内部升序排序
		arr.sort()
		# 按层拼接
		seq.extend(arr)
	# 严格上升子序列长度（牌堆法 + bisect_left）
	tails = []
	for x in seq:
		i = bisect_left(tails, x)
		if i == len(tails):
			tails.append(x)
		else:
			tails[i] = x
	print(len(tails))

if __name__ == "__main__":
	main()

Java

import java.io.*;
import java.util.*;

public class Main {
	static class FastScanner {
		private final InputStream in;
		private final byte[] buffer = new byte[1 << 16];
		private int ptr = 0, len = 0;
		FastScanner(InputStream is) { in = is; }
		private int read() throws IOException {
			if (ptr >= len) {
				len = in.read(buffer);
				ptr = 0;
				if (len <= 0) return -1;
			}
			return buffer[ptr++];
		}
		int nextInt() throws IOException {
			int c, s = 1, x = 0;
			do { c = read(); } while (c <= 32 && c != -1);
			if (c == '-') { s = -1; c = read(); }
			for (; c > 32; c = read()) x = x * 10 + (c - '0');
			return x * s;
		}
	}

	public static void main(String[] args) throws Exception {
		FastScanner fs = new FastScanner(System.in);
		int n;
		try {
			n = fs.nextInt();
		} catch (Exception e) {
			return;
		}
		// 总量不超过 2e5，直接用 ArrayList 存
		ArrayList<Integer> seq = new ArrayList<>(200000);
		for (int i = 0; i < n; i++) {
			int m = fs.nextInt();
			int[] arr = new int[m];
			for (int j = 0; j < m; j++) arr[j] = fs.nextInt();
			// 每层内部升序排序
			Arrays.sort(arr);
			// 按层拼接
			for (int x : arr) seq.add(x);
		}
		// 严格上升子序列长度（牌堆法 + lower_bound）
		int[] tails = new int[seq.size()];
		int len = 0;
		for (int x : seq) {
			int pos = lowerBound(tails, 0, len, x);
			tails[pos] = x;
			if (pos == len) len++;
		}
		System.out.println(len);
	}

	// 在 [l, r) 上找第一个 >= x 的位置
	static int lowerBound(int[] a, int l, int r, int x) {
		while (l < r) {
			int mid = (l + r) >>> 1;
			if (a[mid] >= x) r = mid;
			else l = mid + 1;
		}
		return l;
	}
}

题目内容

Tk 是一个战斗狂，秉承着战斗爽的理念，他隐藏了自己无敌的战力，现冒充一个毫无威胁的小萌新参加爬榜竞赛。裁判测试后，Tk 的初始战斗力定为 $1$ 。

比赛共有 $n$ 个分级，编号为 $1$ 至 $n$ ；第 $i$ 个分级包含 $m_i$ 名选手，其中第 $j$ 名选手的战斗力为 $a_{ij}$ 。

Tk 初始位于第 $1$ 个分级，比赛过程中，他会反复执行以下两种操作之一，直到无法继续。

• 在当前分级中，选择一名战斗力不低于自己当前战斗力的选手 $a_{ij}$ 并击败该选手；此时击败数加 $1$ ，且 Tk 的战斗力被重置为 $a_{ij}+1$ ；

• 如果此时分级编号不为 $n$ 选择进入下一个分级，即分级编号加 $1$ ；该操作不可逆，一旦进入无法返回。

Tk 对比赛本身不感兴趣，他只想知道最多可以击败多少名选手，请输出这个最大击败数。

输入描述

第一行输入一个整数 $n(1≦n≦10^4)$ ，表示分级数；

接下来 $n$ 行，第 $i$ 行首先输入一个整数 $m_i(1≦m_i≦2×10^5)$ ，表示第 $i$ 个分级的选手人数；随后输入 $m_i$ 个整数 $a_{i,1},a_{i,2},...,a_{i,m_i}(1≦a_{i,j}≦10^9)$ ，表示每位选手的战斗力；

除此之外，保证所有分级中 $m_i$ 之和不超过 $2×10^5$ 。

输出描述

输出一个整数，表示 Tk 在比赛中能够击败的最多选手数。

样例1

输入

2
2 1 8
4 2 3 4 5

输出

5

说明

对于此样例，在第一层击败战斗力为 $1$ 的人，Tk 战斗力重置为 $2$ ，前往第二层，在第二层击败战斗力为 $2$ 的人，战斗力重置为 $3$ ，在第二层击败战斗力为 $3$ 的人，战斗力重置为 $4$ ，在第二层击败战斗力为 $4$ 的人，战斗力重置为 $5$ ，在第二层击败战斗力为 $5$ 的人，战斗力重置为 $6$ 。

样例2

输入

2
2 1 1
3 2 2 2

输出

2