票务网站模板,wordpress移动端导航,网站域名的组成,广州小程序开发报价一、题目
1、题目描述 2、输入输出
2.1输入 2.2输出 3、原题链接
Problem - 1237D - Codeforces 二、解题报告
1、思路分析
case3提示我们一件事情#xff1a;如果存在某个位置永远不停止#xff0c;那么所有位置都满足永远不停止
很容易证明
随着下标右移#xff0c…一、题目
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::pairint, 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;
}templateclass T, int M
struct ST {T n;std::vectorT nums;std::vectorT log2;std::vectorstd::arrayT, M f0, f1;ST (T _n, std::vectorT _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::arrayT, 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::vectorint a(N * 2);for (int i 0; i N; i ) std::cin a[i], a[i N] a[i];STint, 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::vectorint 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;
}
