題目的難度顏色使用 Luogu 上的分級，由簡單到困難分別為 🔴🟠🟡🟢🔵🟣⚫。

🔗 ABC436F Starry Landscape Photo

Problem Statement

題目簡述

夜空中有 NN 顆星星排成一列，第 ii 顆星星（從東邊數起，1-indexed）的亮度排名為 BiB_i（1≤Bi≤N1 \le B_i \le N，且 BB 為排列）。
拍照時需選擇一個連續區間 [l,r][l, r] 和一個亮度閾值 bb，照片會包含該區間內所有亮度排名 ≤b\le b 的星星（即最亮的 bb 顆星範圍內）。
求能拍出的不同星星集合的數量（空集合除外）。

具體描述

透過指定 (l,r,b)(l, r, b) 組合，可以得到一個星星集合。
求在所有可能的 (l,r,b)(l, r, b) 組合中，所能得到的不同星星集合數量。

Constraints

約束條件

  • 1≤N≤5×1051 \le N \le 5 \times 10^5
  • BB 是 (1,…,N)(1, \dots, N) 的一個排列。

思路：枚舉集合的最大值中心

解題思路

這道題的核心在於如何不重不漏地計算每一個可能的星星集合。
由於集合是由「最大亮度排名 bb」截斷產生的，對於任意一個符合條件的集合，其中 BB 值最大的那顆星星是唯一的。我們可以利用這個性質，將每個集合唯一映射到其「BB 值最大的元素」上進行統計。

方法一：按照亮度從小到大枚舉星星，對下標維護 BIT

1. 以「最大亮度星星」為中心

假設某個集合 SS 中 BB 值最大的星星是 xx（位置 idxidx，亮度 v=Bidxv = B_{idx}）。
那麼這個集合 SS 必然滿足：

  1. x∈Sx \in S。
  2. SS 中所有其他元素的亮度都 <v< v。
  3. SS 是由位置 idxidx 左右兩側延伸出去的某些「亮度 ≤v\le v 的星星」所組成的。

具體來說，如果我們只看亮度 ≤v\le v 的星星，那麼 SS 就是包含 idxidx 的一個連續段。
因此，問題轉化為：對於每一顆星星（當作最大值中心），在只保留亮度 ≤Bidx\le B_{idx} 的星星的情況下，有多少個包含 idxidx 的連續區間？

2. 利用 BIT 進行計數

我們可以按照亮度 v=1v = 1 到 NN 的順序枚舉星星：

  • 當處理亮度為 vv 的星星（位置 idxidx）時，我們希望知道在它左邊和右邊分別有多少個位置 jj 滿足 Bj≤vB_j \le v。
  • 利用 Fenwick Tree (BIT) 維護位置資訊。每處理一個亮度 vv，就將其位置 idxidx 加入 BIT。
  • 查詢：
    • cntLcnt_L：idxidx 左側（含 idxidx）已加入 BIT 的星星數量。
    • cntRcnt_R：idxidx 右側（含 idxidx）已加入 BIT 的星星數量。
  • 根據乘法原理，以該星星為最大值的合法集合數為 cntL×cntRcnt_L \times cnt_R。這相當於在左側可選的範圍中選一個起點，在右側可選的範圍中選一個終點。
結論

總答案即為所有星星作為中心時 cntL×cntRcnt_L \times cnt_R 的總和。

複雜度分析

  • 時間複雜度：O(Nlog⁡N)\mathcal{O}(N \log N)。
  • 空間複雜度：O(N)\mathcal{O}(N)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
from atcoder.fenwicktree import FenwickTree

def solve():
    N = int(input())
    B = list(map(int, input().split()))
    assert len(B) == N

    # 紀錄每個亮度對應的星星位置
    pos = [0] * (N + 1)
    for i, b in enumerate(B):
        pos[b] = i

    ans = 0
    bit = FenwickTree(N)
    for b in range(1, N + 1):
        idx = pos[b]
        # 將當前亮度 b 的星星位置加入 BIT
        # 此時 BIT 中存在的點都是亮度 <= b 的點
        bit.add(idx, 1)
        # 計算以當前星星為最大值的合法集合數
        ans += bit.sum(0, idx + 1) * bit.sum(idx, N)  # [l, r)
    print(ans)

if __name__ == '__main__':
    solve()

方法二：按照下標順序枚舉星星，對亮度的值域維護 BIT

這個方法雖然遍歷順序不同，但數學意義上完全等價，依然是計算「以當前星星為最大值」的集合數量。

1. 調整維護的對象

我們按照位置順序 i=0…N−1i = 0 \dots N-1 遍歷星星。

  • 對於當前星星 ii，其亮度為 b=Bib = B_i。
  • 左邊比我小的數量 (cntLcnt_L)：
    • 使用 BIT 維護「目前已遍歷過的星星的亮度分佈」。
    • 查詢 bit.sum(0, b) 即為 ii 左側亮度 <b< b 的星星數量。
    • 加上自己，則 cntL=bit.sum(0,b)+1cnt_L = \text{bit.sum}(0, b) + 1。
  • 右邊比我小的數量 (cntRcnt_R)：
    • 這裡利用了一個巧妙的性質：整個陣列中，亮度 <b< b 的星星總共有 b−1b-1 顆（因為 BB 是 1…N1 \dots N 的排列）。
    • 其中有 cntL−1cnt_L - 1 顆已經在左側出現過了。
    • 因此，剩下的必定在右側。
    • cntR=[(b−1)−(cntL−1)]+1=b−cntL+1cnt_R = [(b - 1) - (cnt_L - 1)] + 1 = b - cnt_L + 1。

透過這種方式，我們省去了對右側的顯式查詢，僅需一次遍歷與一個維護值域的 BIT。

複雜度分析

  • 時間複雜度：O(Nlog⁡N)\mathcal{O}(N \log N)。
  • 空間複雜度：O(N)\mathcal{O}(N)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
from atcoder.fenwicktree import FenwickTree

def solve():
    N = int(input())
    B = list(map(int, input().split()))
    assert len(B) == N

    ans = 0
    bit = FenwickTree(N)
    for b in B:
        # 總共有 b - 1 個亮度小於 b 的星星
        # bit 中對值域維護了左側的星星，因此左側亮度小於 b 的星星數為 bit.sum(0, b)
        left = bit.sum(0, b)
        # 右側亮度小於 b 的星星數為 b - 1 - left
        right = b - 1 - left
        # 以當前星星為最大值的合法集合數
        ans += (left + 1) * (right + 1)
        bit.add(b - 1, 1)
    print(ans)

if __name__ == '__main__':
    solve()

兩種寫法的比較

雖然兩者最終計算的公式皆為 Ans=∑(左邊≤Bi)×(右邊≤Bi)Ans = \sum (\text{左邊} \le B_i) \times (\text{右邊} \le B_i)，但在實作視角上有顯著差異。

特徵 方法一 方法二
遍歷順序 按亮度 (1→N1 \to N) 按位置 (0→N−10 \to N-1)
BIT 維護內容 維護位置的出現情況 維護亮度的出現情況
BIT 查詢意義 query(0, pos): 查位置區間和 query(0, val): 查值域區間和
計算 cntLcnt_L 直接查 BIT (因為 BIT 裡只有比我小的星) 查 BIT (統計目前遍歷過且比我小的)
計算 cntRcnt_R 直接查 BIT 利用全域性質推算：總共比我小的 - 左邊比我小的

優劣分析：

  • 方法二 更優雅：
    • 不需要預處理 pos 陣列（不需反查亮度對應的位置）。
    • 只需要一次遍歷輸入陣列 BB。
    • 充分利用了「排列」的性質 (比 bb 小的有 b−1b-1 個) 來推算右側數量。
  • 方法一 更直觀：
    • 「按亮度從小到大加入」是處理數值限制問題的經典技巧（類似 Kruskal 或離線查詢）。
    • 思路線性單純：先把小的放進去，查詢時場上存在的都是合法的。

寫在最後

PROMPT