Starry Landscape Photo题解

u822844 · 2025-12-16 00:41:43 · 题解

题意简述

因为前 b 排名就是所有 B_i \le b 的情况，且每颗星星的位置固定，所以可以认为是构造集合，原题就相当于：

序列 B_1,B_2,\dots,B_n 是 1,2,3,\dots,n 的一个排列，对于正整数 1 \le l < r \le n 与 1 \le b \le n，有非空集合

T = \{ B_i \mid l \le i \le r \text{ and } B_i \le b \}

求共有多少种不同的 T。

暴力

考虑枚举所有的 l,r,b，并且还需要维护一个散列表进行去重，时空复杂度都是 O(n^3)，按照数据范围 5 \times 10^5，不可能成功。

正解

推理

因为枚举决定集合的参数 l,r,b 完全不可能，自然地，开始观察集合中的元素。
由于 b 规定了集合所有元素值的上限，我们注意到：

• 每一个 T，一定有一个最大值 \max(T) \le b。既然其为最大值，那么将 b 改为 \max(T) 后生成的集合也一定与 T 完全一样，因为原集合中没有 (\max(T), b] 间的数字。

因此不需要关注 b 的具体值，我们只需要统计对于每个 m，\max(T)=m 的集合有多少种并累加即可。枚举 m=1\dots n 是可行的。

而当 \max(T)=m 时，一定有：

• m \in T
• T$ 中每个元素都 $\le m

那么就相当于把原序列中所有大于 m 的数字全部扣掉，只剩下 1,2,\dots,m，在这个保留的序列中，这些数字的相对位置不变。所以，这个合法集合就一定是剩下序列中的一个连续子段。

于是，问题就分解成了：对于每一个 m，如果只保留原序列中 \le m 的数字，形成一个新的序列 S_m，求 S_m 中有多少个包含 m 的连续子段。

编码

要遍历每一个 m=1\dots n，我们需要知道 m 在原数组的位置，即 B_i=m 时的 i，这就需要预处理一个位置数组：

// global
int p[500005];
// main
for (int i = 1; i <= n; i++) {
    cin >> a[i];
    p[a[i]] = i;
}

然后进行循环，对于每一个 m，不能每次都重新构造整个 \{S_m\}（时间复杂度 O(n^2)，虽然比暴力快很多但是仍然不够...）。
但是，如果从小到大循环，则上一次的所有元素一定也在这次的保留序列中，也就是集合 S_{m-1} \subset S_m，而对于连续子段 [l,r]，可以发现：

• 左端点 l 一定在 S_m 的第一个元素和 m 的位置之间
• 右端点 r 一定在 m 和 S_m 的最后一个元素之间

由于枚举顺序，明显 S_m 只比 S_{m-1} 多出了 m 这个数，我们就可以每循环一次，为当前的 m 进行标记，查询在 p_m 之前的标记数量就是 k（注意 p_m 也要算上）。
单点修改，区间查询，最合适的数据结构是——树状数组！

// global
int tree[500005];
int lowbit(int x) {
    return x & (-x);
}
void add(int x, int v) {
    for (; x <= n; x += lowbit(x)) {
        tree[x] += v; 
    } 
}
int query(int x) {
    int res = 0;
    for (; x > 0; x -= lowbit(x)) {
        res += tree[x];
    }
    return res;
}

最后，对于 m，总共可能的区间个数是其左端点的个数和右端点个数的积（乘法原理），即：

// main
ll res = 0;
for (int i = 1; i <= n; ++i) {
    int pos = p[i];
    int k = query(pos) + 1;
    res += (ll)k * (i - k + 1);
    add(pos, 1);
}
cout << res << endl;

完整代码 | Accepted