题目形容
这是 LeetCode 上的 1395. 统计作战单位数 ，难度为 中等。
Tag : 「树状数组」、「容斥原理」
n 名士兵站成一排。每个士兵都有一个 举世无双 的评分 rating 。
每 $3$ 个士兵能够组成一个作战单位，分组规定如下：
- 从队伍中选出下标别离为
i、j、k的 $3$ 名士兵，他们的评分别离为 $rating[i]$、$rating[j]$、$rating[k]$ - 作战单位需满足： $rating[i] < rating[j] < rating[k]$ 或者 $rating[i] > rating[j] > rating[k]$ ，其中 $0 <= i < j < k < n$
请你返回按上述条件能够组建的作战单位数量。每个士兵都能够是多个作战单位的一部分。
示例 1：
输出：rating = [2,5,3,4,1]输入：3解释：咱们能够组建三个作战单位 (2,3,4)、(5,4,1)、(5,3,1) 。示例 2：
输出：rating = [2,1,3]输入：0解释：依据题目条件，咱们无奈组建作战单位。示例 3：
输出：rating = [1,2,3,4]输入：4提醒：
- $n == rating.length$
- $3 <= n <= 1000$
- $1 <= rating[i] <= 10^5$
rating中的元素都是惟一的
根本剖析
为了不便，咱们记 rating 为 rs。
题目实质是要咱们统计所有满足「递增」或「递加」的三元组。换句话说，对于每个 $t = rs[i]$ 而言，咱们须要统计比其 $t$ 大或比 $t$ 小的数的个数。
问题波及「单点批改（更新数值 $t$ 的呈现次数）」以及「区间查问（查问某段范畴内数的个数）」，应用「树状数组」求解较为适合。
树状数组 - 枚举两端
一个奢侈的想法是，对于三元组 $(i, j, k)$，咱们枚举其两端 $i$ 和 $k$，依据 $rs[i]$ 和 $rs[k]$ 的大小关系，查问范畴 $[i + 1, k - 1]$ 之间非法的数的个数。
在确定左端点 $i$ 时，咱们从 $i + 1$ 开始「从小到大」枚举右端点 $k$，并将遍历过程中通过的 $rs[k]$ 增加到树状数组进行计数。
处理过程中依据 $a = rs[i]$ 和 $b = rs[k]$ 的大小关系进行分状况探讨：
- 当 $a < b$ 时，咱们须要在范畴 $[i + 1, k - 1]$ 中找「大于 $a$」同时「小于 $b$」的数的个数，即
query(b - 1) - query(a) - 当 $a > b$ 时，咱们须要在范畴 $[i + 1, k - 1]$ 中找「小于 $a$」同时「大于 $b$」的数的个数，即
query(a - 1) - query(b)
一些细节：显然咱们须要在枚举每个左端点 $i$ 时清空树状数组，但留神不能应用诸如 Arrays.fill(tr, 0) 的形式进行清空。
因为在没有离散化的状况下，树状数组的大小为 $m = 1e5$，即执行 Arrays.fill 操作的复杂度为 $O(m)$，这会导致咱们计算量为至多为 $n \times m = 1e8$，会有 TLE 危险。
因而一个适合做法是：在 $[i + 1, n - 1]$ 范畴内枚举完 $k$ 后（进行的是 +1 计数），再枚举一次 $[i + 1, n - 1]$ 进行一次 -1 的计数进行对消。
代码：
class Solution { static int N = (int)1e5 + 10; static int[] tr = new int[N]; int lowbit(int x) { return x & -x; } void update(int x, int v) { for (int i = x; i < N; i += lowbit(i)) tr[i] += v; } int query(int x) { int ans = 0; for (int i = x; i > 0; i -= lowbit(i)) ans += tr[i]; return ans; } public int numTeams(int[] rs) { int n = rs.length, ans = 0; for (int i = 0; i < n; i++) { int a = rs[i]; for (int j = i + 1; j < n; j++) { int b = rs[j]; if (a < b) ans += query(b - 1) - query(a); else ans += query(a - 1) - query(b); update(b, 1); } for (int j = i + 1; j < n; j++) update(rs[j], -1); } return ans; }}- 工夫复杂度：令 $m = 1e5$ 为值域大小，整体复杂度为 $O(n^2\log{m})$
- 空间复杂度：$O(m)$
双树状数组优化 - 枚举中点
咱们思考将 $n$ 的数据范畴晋升到 $1e4$ 该如何做。
上述解法的瓶颈在于咱们枚举三元组中的左右端点，复杂度为 $O(n^2)$，而实际上利用三元组必然递增或递加的个性，咱们能够调整为枚举起点 $j$，从而将「枚举点对」调整为「枚举中点」，复杂度为 $O(n)$。
假如以后枚举到的点为 $rs[i]$，问题转换为在 $[0, i - 1]$ 有多少比 $rs[i]$ 小/大 的数，在 $[i + 1, n - 1]$ 有多少比 $rs[i]$ 大/小 的数，而后汇合「乘法」原理即可晓得 $rs[i]$ 作为三元组中点的非法计划数。
统计 $rs[i]$ 右边的比 $rs[i]$ 大/小 的数很好做，只须要在「从小到大」枚举 $i$ 的过程中，将 $rs[i]$ 增加到树状数组 tr1 即可。
对于统计 $rs[i]$ 左边比 $rs[i]$ 小/大 的数，则须要通过「对消计数」来做，起始咱们先将所有 $rs[idx]$ 退出到另外一个树状数组 tr2 中（进行 +1 计数），而后在从前往后解决每个 $rs[i]$ 的时候，在 tr2 中进行 -1 对消，从而确保咱们解决每个 $rs[i]$ 时，tr1 存储右边的数，tr2 存储左边的数。
代码：
class Solution { static int N = (int)1e5 + 10; static int[] tr1 = new int[N], tr2 = new int[N]; int lowbit(int x) { return x & -x; } void update(int[] tr, int x, int v) { for (int i = x; i < N; i += lowbit(i)) tr[i] += v; } int query(int[] tr, int x) { int ans = 0; for (int i = x; i > 0; i -= lowbit(i)) ans += tr[i]; return ans; } public int numTeams(int[] rs) { int n = rs.length, ans = 0; Arrays.fill(tr1, 0); Arrays.fill(tr2, 0); for (int i : rs) update(tr2, i, 1); for (int i = 0; i < n; i++) { int t = rs[i]; update(tr2, t, -1); ans += query(tr1, t - 1) * (query(tr2, N - 1) - query(tr2, t)); ans += (query(tr1, N - 1) - query(tr1, t)) * query(tr2, t - 1); update(tr1, t, 1); } return ans; }}- 工夫复杂度：令 $m = 1e5$ 为值域大小，整体复杂度为 $O(n\log{m})$
- 空间复杂度：$O(m)$
最初
这是咱们「刷穿 LeetCode」系列文章的第 No.1395 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，局部是有锁题，咱们将先把所有不带锁的题目刷完。
在这个系列文章外面，除了解说解题思路以外，还会尽可能给出最为简洁的代码。如果波及通解还会相应的代码模板。
为了不便各位同学可能电脑上进行调试和提交代码，我建设了相干的仓库：https://github.com/SharingSou... 。
在仓库地址里，你能够看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其余优选题解。
更多更全更热门的「口试/面试」相干的材料可拜访排版精明的 合集新基地
本文由mdnice多平台公布