一、题目
1、题目描述
2、输入输出
2.1输入
2.2输出
3、原题链接
Problem - 1237D - Codeforces
二、解题报告
1、思路分析
case3提示我们一件事情:如果存在某个位置永远不停止,那么所有位置都满足永远不停止
很容易证明
随着下标右移,区间最大值不会变大,那么后面2倍大于旧的最大值的数的二倍仍然大于新的最大值
那么对于每个位置我们要找到第一个满足a[i] < max / 2的 i
我们可以st表预处理出区间最大值最小值
然后对于递推求解ans
对于i,我们二分查找找到第一个大于a[i]的j,同样二分查找找到第一个a[k] < a[i]的k
如果k < j,那么显然答案就是j - i
否则, ans[i] = k - i + ans[k % N]
我们建立了递推关系,一共N个状态,每个状态O(log)转移,总体时间复杂度就是O(NlogN)
2、复杂度
时间复杂度: O(NlogN)空间复杂度:O(NlogN)
3、代码详解
#include <bits/stdc++.h>
using i64 = long long;
using i128 = __int128;
using PII = std::pair<int, int>;
std::ostream& operator<< (std::ostream& out, i128 x) {
std::string s;
while (x) s += ((x % 10) ^ 48), x /= 10;
std::reverse(s.begin(), s.end());
return out << s;
}
template<class T, int M>
struct ST {
T n;
std::vector<T> nums;
std::vector<T> log2;
std::vector<std::array<T, M>> f0, f1;
ST (T _n, std::vector<T>& _nums): n(_n), nums(_nums), log2(_n + 1), f0(_n), f1(_n) {
log2[2] = 1;
for (int i = 3; i <= n; i ++ ) log2[i] = log2[i >> 1] + 1;
for (int i = 0; i < n; i ++ ) f0[i][0] = f1[i][0] = nums[i];
for (int j = 1; j < M; j ++ )
for (int i = 0; i < n && i + (1 << (j - 1)) < n; i ++ )
f0[i][j] = std::max(f0[i][j - 1], f0[i + (1 << (j - 1))][j - 1]),
f1[i][j] = std::min(f1[i][j - 1], f1[i + (1 << (j - 1))][j - 1]);
}
std::array<T, 2> query(int l, int r) {
int k = log2[r - l + 1];
return { std::max(f0[l][k], f0[r - (1 << k) + 1][k]),
std::min(f1[l][k], f1[r - (1 << k) + 1][k]) };
}
};
void solve() {
int N;
std::cin >> N;
std::vector<int> a(N * 2);
for (int i = 0; i < N; i ++ )
std::cin >> a[i], a[i + N] = a[i];
ST<int, 18> st(N * 2, a);
if (st.query(0, N - 1)[0] <= st.query(0, N - 1)[1] * 2LL) {
for (int i = 0; i < N; i ++ ) std::cout << -1 << " \n"[i == N - 1];
return;
}
std::vector<int> ans(N, -1);
auto findmi = [&](int l, int r) -> int {
int x = a[l - 1];
while (l < r) {
int mid = l + r >> 1;
auto [ma, mi] = st.query(l, mid);
if (mi * 2LL < x) r = mid;
else l = mid + 1;
}
return l;
};
auto findma = [&](int l, int r) -> int {
int x = a[l - 1];
while (l < r) {
int mid = l + r >> 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 < gt) return ans[x] = lt - x;
return ans[x] = gt - x + self(self, gt % N);
};
for (int i = 0; i < N; i ++ )
std::cout << dfs(dfs, i) << " \n"[i == N - 1];
}
int main(int argc, char** argv) {
std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);
int _ = 1;
// std::cin >> _;
while (_ --)
solve();
return 0;
}