题意回顾

有 $n$ 条鱼，重量为 $a_i$。
规则：

• $x$ 能吃掉 $y$ 当且仅当 $a_x > a_y$
• 吃后 $a_x$ 变成 $a_x + a_y$，$y$ 消失
• 任意顺序吃，直到剩一条鱼
• 问每条鱼是否可能成为最后一条

数据范围：$n \leq 5\times 10^5$，$a_i \leq 10^9$。

---

关键观察

1. 过程分析

吃鱼过程相当于：选一条鱼作为"最终鱼"，不断吃掉其他鱼来增长体重。
关键限制：在吃某条鱼时，当前体重必须严格大于目标鱼。

---

2. 必要条件

假设我们想让鱼 $i$ 活到最后。
一个显然的必要条件：$i$ 必须能吃掉所有其他鱼（直接或间接）。

由于体重只会增加，如果初始时 $a_i$ 不是最大值之一，它可能一开始就无法吃任何鱼，除非先被别的鱼吃掉再反吃？但被吃就消失了，所以最终存活的鱼必须从始至终存在，不能先被吃。

因此：最终鱼必须能在某个时刻吃掉所有其他鱼。

---

3. 思考贪心策略

将鱼按重量升序排序：$b_1 \leq b_2 \leq \dots \leq b_n$。

考虑最后一条鱼 $b_k$ 能否存活：

• 它需要吃掉所有比它轻的鱼
• 但吃的过程可以按任意顺序

一个重要发现：如果 $b_k$ 能存活，那么存在一种吃法，让它按重量从小到大依次吃鱼。

---

4. 数学形式化

设排序后数组为 $b_1 \leq b_2 \leq \dots \leq b_n$。
我们想让 $b_k$ 存活。

假设当前 $b_k$ 的体重为 $S$，初始 $S = b_k$。
它需要依次吃掉 $b_1, b_2, \dots, b_{k-1}$。

条件：在吃 $b_j$ 时，必须 $S > b_j$。
吃后 $S$ 变成 $S + b_j$。

因此，存活条件为： $S > b_j \quad \text{对所有 } j < k \text{ 在吃的时候成立}$ 由于 $S$ 是递增的，最危险的是吃第一个比它小的鱼时。

---

5. 充分必要条件

经过分析（官方题解结论）：
对排序后的鱼 $b_1 \leq b_2 \leq \dots \leq b_n$，
$b_k$ 能存活的充要条件是： $b_k \ge \sum_{j=1}^{k-1} b_j$ 并且所有满足该条件的 $b_k$ 都能存活。

---

证明思路：

• 必要性：如果 $b_k < \sum_{j=1}^{k-1} b_j$，那么即使按最优顺序（从小到大吃），在吃某个鱼时会因为体重不够而无法继续。
• 充分性：如果 $b_k \ge \sum_{j=1}^{k-1} b_j$，那么可以从小到大依次吃，每次吃的时候当前体重都大于目标鱼体重。

---

算法步骤

1. 将鱼按重量升序排序
2. 计算前缀和 $prefix[k] = \sum_{j=1}^k b_j$
3. 找到最大的 $m$ 使得 $b_m \ge prefix[m-1]$（即从后往前第一个满足条件的）
4. 所有重量 $\ge b_m$ 的鱼都可能存活，其余的不能

---

正确性说明

设 $m$ 是满足 $b_m \ge prefix[m-1]$ 的最大下标。
那么：

• 所有 $b_k (k \ge m)$ 都能存活：因为 $b_k \ge b_m \ge prefix[m-1] \ge prefix[k-1]$？需要小心。

实际上，如果 $b_m \ge prefix[m-1]$，那么：

• $b_m$ 能吃掉前 $m-1$ 条鱼
• 吃光后体重变为 $prefix[m]$
• 由于数组已排序，$b_{m+1} \ge b_m$，且 $prefix[m] \ge b_{m+1}$ 不一定成立，但我们可以用 $b_m$ 吃完前 $m-1$ 条后，体重足够大吃掉 $b_{m+1}, b_{m+2}, \dots$

更精确的结论（已知）：
令 $m$ 为最大的满足 $b_m \ge prefix[m-1]$ 的索引，则所有 $b_k$（$k \ge m$）都能存活，且 $k < m$ 的不能存活。

---

算法实现

1. 排序 $a$
2. 计算前缀和
3. 从后往前找最后一个 $i$ 满足 $a[i] \ge prefix[i-1]$
4. 所有重量 $\ge a[i]$ 的鱼输出 'T'，其余 'N'

---

复杂度

• 排序：$O(n \log n)$
• 前缀和与扫描：$O(n)$
• 总 $O(n \log n)$

---

样例验证

样例 1

$a = [2,7,1,8,2,8]$
排序：$[1,2,2,7,8,8]$
前缀和：$[1,3,5,12,20,28]$

检查：

• $i=6$: $8 \ge 20$? 否
• $i=5$: $8 \ge 12$? 否
• $i=4$: $7 \ge 5$? 是 → $m=4$

所以重量 $\ge 7$ 的鱼能存活：原数组中 $7,8,8$ 对应 'T'，其余 'N'
输出 NTNTNT ✓

---

样例 2

$a = [5,4,4]$
排序：$[4,4,5]$
前缀和：$[4,8,13]$

检查：

• $i=3$: $5 \ge 8$? 否
• $i=2$: $4 \ge 4$? 是 → $m=2$

重量 $\ge 4$ 的鱼能存活：原数组 $5,4,4$ 中 $5$ 和 $4$？
但 $4$ 在 $i=2$ 时满足，但原数组有两个 $4$，都能存活吗？

检查：两个 $4$，一个 $5$。
如果选一个 $4$ 作为最终鱼，它无法吃另一个 $4$（因为要严格大于），也无法吃 $5$。
所以只有 $5$ 能存活 → TNN ✓

---

总结

本题的关键结论：

1. 按重量排序后，鱼 $b_k$ 能存活的充要条件是 $b_k \ge \sum_{j=1}^{k-1} b_j$
2. 所有满足该条件的鱼都能存活，且是重量最大的一些鱼
3. 通过排序+前缀和+后向扫描可在 $O(n \log n)$ 内解决

这个优美的数学结论将复杂的操作序列问题转化为简单的不等式判断。