Number of Longest Increasing Subsequence ↗

• Idea: 對每個元素掃描前面所有比它小的元素，維護長度和計數
• Time: O(n^2)
• Space: O(n)

class Solution {
    fun findNumberOfLIS(nums: IntArray): Int {
        val n = nums.size
        val len = IntArray(n) { 1 }
        val cnt = IntArray(n) { 1 }
        var maxLen = 1
        for (i in 1 until n) {
            for (j in 0 until i) {
                if (nums[j] < nums[i]) {
                    if (len[j] + 1 > len[i]) {
                        len[i] = len[j] + 1
                        cnt[i] = cnt[j]
                    } else if (len[j] + 1 == len[i]) {
                        cnt[i] += cnt[j]
                    }
                }
            }
            maxLen = maxOf(maxLen, len[i])
        }
        var result = 0
        for (i in 0 until n) {
            if (len[i] == maxLen) result += cnt[i]
        }
        return result
    }
}

• Idea: 用線段樹在值域上維護 (最長長度, 計數) 對，支援快速查詢和更新
• Time: O(n log n)
• Space: O(n)

class Solution {
    fun findNumberOfLIS(nums: IntArray): Int {
        // 座標壓縮
        val sorted = nums.toSortedSet().toList()
        val rank = HashMap<Int, Int>()
        sorted.forEachIndexed { i, v -> rank[v] = i + 1 }
        val m = sorted.size

        // 線段樹：每個節點存 (maxLen, count)
        val treeLen = IntArray(4 * m)
        val treeCnt = IntArray(4 * m)

        fun merge(len1: Int, cnt1: Int, len2: Int, cnt2: Int): Pair<Int, Int> {
            if (len1 > len2) return len1 to cnt1
            if (len2 > len1) return len2 to cnt2
            return len1 to (cnt1 + cnt2)
        }

        fun query(node: Int, s: Int, e: Int, l: Int, r: Int): Pair<Int, Int> {
            if (r < s || e < l) return 0 to 0
            if (l <= s && e <= r) return treeLen[node] to treeCnt[node]
            val mid = (s + e) / 2
            val left = query(2 * node, s, mid, l, r)
            val right = query(2 * node + 1, mid + 1, e, l, r)
            return merge(left.first, left.second, right.first, right.second)
        }

        fun update(node: Int, s: Int, e: Int, pos: Int, len: Int, cnt: Int) {
            if (s == e) {
                val (ml, mc) = merge(treeLen[node], treeCnt[node], len, cnt)
                treeLen[node] = ml
                treeCnt[node] = mc
                return
            }
            val mid = (s + e) / 2
            if (pos <= mid) update(2 * node, s, mid, pos, len, cnt)
            else update(2 * node + 1, mid + 1, e, pos, len, cnt)
            val (ml, mc) = merge(treeLen[2 * node], treeCnt[2 * node], treeLen[2 * node + 1], treeCnt[2 * node + 1])
            treeLen[node] = ml
            treeCnt[node] = mc
        }

        var maxLen = 0
        var ans = 0
        for (num in nums) {
            val r = rank[num]!!
            val (prevLen, prevCnt) = if (r > 1) query(1, 1, m, 1, r - 1) else 0 to 0
            val curLen = prevLen + 1
            val curCnt = if (prevCnt == 0) 1 else prevCnt
            update(1, 1, m, r, curLen, curCnt)
            if (curLen > maxLen) { maxLen = curLen; ans = curCnt }
            else if (curLen == maxLen) ans += curCnt
        }
        return ans
    }
}