[CF1237D] Balanced Playlist

[CF1237D] Balanced Playlist - 双指针

Description

给定n张唱片，每张唱片都有一个好听度a[i]。某个人选择第i张唱片开始播放，播放完则下一张继续播放，到第n张时下一张为第1张。当某一张唱片的好听度严格小于已经听过的唱片的最大值的一半时，这个人将会停止播放。要求输出对于任意的选择一张唱片i开始，最多能听几张唱片，也可能是无穷多，这时输出-1。

Solution

类似双指针，(i) 为当前枚举起点，(j) 为当前能唱到的终点，显然 (j) 关于 (i) 是单调的

我们控制 (i) 步进，(j) 不断向右移动的过程中，用区间最大值和 (a[j]) 比较

注意数组要复制三份

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 5;

int n, a[N], ans[N], stmax[N][20], lg2[N];

int query_max(int l, int r)
{
    int lg = lg2[r - l];
    return max(stmax[l][lg], stmax[r - (1 << lg) + 1][lg]);
}

bool check(int l, int r)
{
    return 2 * a[r] >= query_max(l, r);
}

signed main()
{
    ios::sync_with_stdio(false);

    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i], a[i + n] = a[i + n + n] = a[i];

    for (int i = 1; i <= 3 * n; i++)
        lg2[i] = log2(i);

    for (int i = 1; i <= 3 * n; i++)
        stmax[i][0] = a[i];
    for (int j = 1; j < 20; j++)
        for (int i = 1; i + (1 << j) - 1 <= 3 * n; i++)
            stmax[i][j] = max(stmax[i][j - 1], stmax[i + (1 << (j - 1))][j - 1]);

    int j = 1;
    for (int i = 1; i <= 3 * n; i++)
    {
        while (j <= 3 * n && check(i, j + 1))
            ++j;
        ans[(i - 1) % n + 1] = max(ans[(i - 1) % n + 1], j - i + 1);
    }

    for (int i = 1; i <= n; i++)
    {
        if (ans[i] >= 2 * n)
            cout << -1 << " ";
        else
            cout << ans[i] << " ";
    }
}