二分+ST表+递推，Cf 1237D - Balanced Playlist

一、题目

1、题目描述

2、输入输出

2.1输入

2.2输出

3、原题链接

Problem - 1237D - Codeforces

---

二、解题报告

1、思路分析

case3提示我们一件事情：如果存在某个位置永远不停止，那么所有位置都满足永远不停止

很容易证明

随着下标右移，区间最大值不会变大，那么后面2倍大于旧的最大值的数的二倍仍然大于新的最大值

那么对于每个位置我们要找到第一个满足a[i]

我们可以st表预处理出区间最大值最小值

然后对于递推求解ans

对于i，我们二分查找找到第一个大于a[i]的j，同样二分查找找到第一个a[k]

如果k

否则, ans[i] = k - i + ans[k % N]

我们建立了递推关系，一共N个状态，每个状态O(log)转移，总体时间复杂度就是O(NlogN)

2、复杂度

时间复杂度： O(NlogN)空间复杂度：O(NlogN)

3、代码详解

 ​

#include 
using i64 = long long;
using i128 = __int128;
using PII = std::pair;
std::ostream& operator> 1;
            auto [ma, mi] = st.query(l, mid);
            if (ma > x) r = mid;
            else l = mid + 1;
        }   
        return l;
    };
    auto dfs = [&](auto&& self, int x) -> int {
        if (~ans[x]) return ans[x];
        int lt = findmi(x + 1, x + N), gt = findma(x + 1, x + N);
        if (lt