题解：P12646 [KOI 2024 Round 1] 升序 & P12642 [KOI 2024 Round 1] 加倍

· · 题解

首先先来看一下这道题的弱化版：P12642 [KOI 2024 Round 1] 加倍。

考虑对于每个 a_i>a_{i+1} 预处理出一个 c_{i} 数组，表示最小的 c_{i} 使得：a_{i+1} \times 2^{c_i} \ge a_i。

我们发现这个 c_i 是可以继承的，即对于某个（另一个）a_j>a_{j+1}，在预处理出最小的 x 使得 a_{j+1} \times 2^x \ge a_j 后，c_j 应该等于 c_{j-1}+x。这是因为之前 c_{j-1} 乘的影响也会作用于此。

所以我们要对 c_i 处理一个前缀和。

但还没完，我们会发现一个问题：对于原本就符合条件的 a_i \le a_{i+1}，如果 a_{i+1} 足够大，大到 a_i \times 2^{c_i} \le a_{i+1}，那么我们之前的修改前缀和相当于是“多了”。

所以我们还要考虑处理出一个大小为负的 c_{i+1} 用于抵消之前并不必要的影响。具体地，找到最大的 x 满足 a_i \times 2^x \le a_{i+1}，则 c_i=-x。

然后考虑如何求答案，我们要先用前缀和“还原”c 数组（因为之前说过 c 数组的影响是顺延的）：s_i = \sum_{k=1}^i c_k。然后再对 s 数组求和：ans=\sum_{i=1}^n s_i。

还有一个细节：可能会出现某个 s_i<0，这属于没有贡献的情况，不能胡乱计入。所以前缀和应该再和 0 取 \max：s_i=\max\{0, s_{i-1}+c_i\}。

void solve()
{
    cin >> n;
    for(int i = 1; i <= n; i ++){
        cin >> a[i];
    }
    for(int i = 1; i <= n - 1; i ++){
        if(a[i] > a[i + 1]){
            int t = a[i + 1];
            while(a[i] > t) t *= 2, c[i] ++;
        }
        else{
            int x = 0, t = a[i];
            while(t * 2 <= a[i + 1]){
              t *= 2, x ++;
            }
            c[i] = -x;
        }
        s[i] = max(0LL, s[i - 1] + c[i]);
    }
    int ans = 0;
    for(int i = 1; i <= n; i ++){
        ans += s[i];
    }
    cout << ans << '\n';
}

下面是加强版（本题）。

还是接着弱化版思路中的 c 数组考虑。对于区间 [l,r]，我们最终的答案是这样的：

\sum\limits_{i=l}^{r} \max\left\{ \bigg(\sum\limits_{j=l}^i c_j \bigg), 0 \right\}

或

\sum_{i=l}^{r} \max(s_i - s_{l-1}, 0)

和 0 取 \max 其实很烦人。这里先考虑如果没有这一层取 \max 的话应该怎么算，可以交换求和符号并结合前缀和进行化简：

\begin{align*} \sum_{i=l}^{r} \sum_{j=l}^i c_j &= \sum_{j=l}^{r} \sum_{i=j}^{r} c_j \\ &= \sum_{j=l}^{r} (r-j+1)c_j \\ &= \sum_{i=l}^{r} (r-i+1)c_i \\ &= \sum_{i=l}^{r} \big((r+1) \cdot c_i - i \cdot c_i \big) \\ &= (r+1) \times \sum_{i=l}^{r} c_i - \sum_{i=l}^{r} i \cdot c_i \end{align*}

解释一下第一步：根据初始公式可知 i \ge j 且 i \le r，把 j 挪到外面后内层 i 的求和范围就出来了。

显然只要预处理出 c_i 的前缀和与 i \cdot c_i 的前缀和就能做到 O(1) 求。

注：在计算时请搞清楚左右端点的包含关系，以及我们当前的计算公式的针对情况、当前算的 c 数组的下标范围等边界情况。在我的代码里会注明。

然后看正常情况。我们的瓶颈就在于和 0 取 \max 实际上会导致求和中断一段（这一段里的前缀和都小于等于 0），然后再接着求。所以我们会很自然地想到能否把非零段都提取出来，然后用上面说的方法快速计算。

考虑预处理出对于所有的 i \in [1,n] 右边第一个会求和中断的位置 p_i，这样就能从有值的位置跳到距离最近的断点（最后一个前缀和不为 0 的位置），就能做了。这其实是一个类似“跳表”的结构。

但时间复杂度呢？或者说， 对于每个询问的 [l,r] 最多能跳多少次？感觉像是 \log 的，实际也的确如此。考虑什么时候会出现 s_i<0，一定是前一个数比后一个数大了至少两倍，这样才会出现 c 是负数用来抵消的情况。而 a 数组的值域是 10^9，也就是说我们最多只会跳 \log_2 10^9 次。

时间复杂度 O(n + q \log w)，w 是 a_i 的值域。

#include <bits/stdc++.h>
#define int long long // ll！！！
using namespace std;
const int maxn = 3e5 + 7;

int n, q, a[maxn], c[maxn], p[maxn], s[maxn], s2[maxn];
stack<int> st;

void solve()
{
    cin >> n >> q;
    for(int i = 1; i <= n; i ++){
        cin >> a[i];
    }

    // 统计c数组
    for(int i = 1; i <= n - 1; i ++){
        if(a[i] > a[i + 1]){
            int t = a[i + 1];
            while(a[i] > t) t *= 2, c[i] ++;
        }
        else{
            int x = 0, t = a[i];
            while(t * 2 <= a[i + 1]){
                t *= 2, x ++;
            }
            c[i] = -x;
        }
    }

    // 预处理前缀和
    for(int i = 1; i <= n; i ++){
        s[i] = s[i - 1] + c[i];
        s2[i] = s2[i - 1] + i * c[i];
    }

    // 预处理p[i]
    for(int i = n; i >= 0; i --){
        while(!st.empty() && s[st.top()] >= s[i]) st.pop(); // 找右边第一个小于s[i]的元素
        p[i] = !st.empty()? st.top() : n + 1; // 如果没有，就赋值n+1
        st.push(i);
    }

    auto sum = [&](int l, int r){ // 快速计算非零的区间前缀和
        return (r + 1) * (s[r] - s[l - 1]) - (s2[r] - s2[l - 1]);
    };

    while(q --){
        int l, r; cin >> l >> r;
        if(l == r){
            cout << 0 << '\n'; continue;
        }
        int ans = 0;
        int i = l - 1; // 我们默认i是前缀和<0的位置，也就是i+1才是前缀和非0的位置。所以注意i从l-1开始。
        while(i <= r - 1){ // 有效的范围应该是l ~ r-1，因为c[r]指的是位置r对r+1的操作次数，不计入在内
            ans += sum(i + 1, min(p[i] - 1, r - 1));
            i = p[i];
        }
        cout << ans << '\n';
    }
}

signed main()
{
    ios :: sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    solve();
    return 0;
}