第2题

给定一个 $1$ 到 $n$ 的排列 $p_1,p_2,\ldots,p_n$，请统计排列中所有长度大于等于 $2$ 的连续子序列的次大数之和。

定义 $\max_2(a_i,a_{i+1},\ldots,a_j)$ 表示从 $a_i$ 开始到 $a_j$ 结束的连续子序列中，排名第二大的数，这个数就是一个连续子序列的次大数之和。

题目就是要求：

$$\sum_{1 \le i < j \le n} \max_2(a_i,a_{i+1},\ldots,a_j)$$

solve 用于解决这个问题。

int q[maxn];
int prev[maxn];
int next[maxn];
long long solve(int n, int p[])
{
    for (int i = 1; i <= n; ++i)
    {
        ____(1)____ ;
    }
    p[0] = q[0] = prev[0] = 0;
    p[n+1] = q[n+1] = next[n+1] = n+1;
    for (int i = 1; i <= n; ++i)
    {
        int num = ____(2)____;
        int prev_num = p[i-1];
        int next_num = p[i+1];
        prev[num] = ____(3)____;
        next[num] = ____(4)____;
    }
    long long sum = 0;
    for (int num = 1; num <= n; ++num) {
        int prev_num = prev[num];
        int prev_prev_num = prev[prev_num];

        int next_num = next[num];
        int next_next_num = next[next_num];

        sum += (long long) num * ____(5)____ * (q[next_num] - q[num]);
        sum += (long long) num * (q[num] - q[prev_num]) * ____(6)____ ;

        ____(7)____ = prev_num;
        ____(8)____ = next_num;
    }
    return sum;
}

(1) 处应填（ ）。

{{ select(1) }}

• q[p[i]] = i
• q[i] = p[i]
• q[i] = 1
• q[i] = i