https://codeforces.com/contest/1923/problem/D

题意

有 $n$ 个史莱姆排成一行。这些史莱姆从左到右依次编号为 $1$ 到 $n$。第 $i$ 个黏液的大小是 $a_i$。

每秒钟都会发生以下情况正好有一个史莱姆吃掉它的一个邻居，并按照被吃邻居的大小来增加自己的大小。只有当一个史莱姆的大小严格大于它的邻居时，它才能吃掉它的邻居。如果没有严格意义上比它的邻居大的史莱姆，这个过程就结束了。

对于每一个史莱姆，计算这个史莱姆被另一个史莱姆吃掉所需的最少秒数，或者报告说这是不可能的。

题解

现在我们要求出第 $i$ 个史莱姆被另一个史莱姆吃掉的最少秒数。

在任意秒数后，每个粘液的大小等于某个子数组的总和。吃掉 $i$ 的应该是它的邻居（可能是一个子数组的总和）。因此，吃掉它的史莱姆的大小等于某个 $j<i$ 的子数组 $[j, i-1]$ 或某个 $j>i$ 的子数组 $[i + 1, j]$ 的和。我们需要了解哪一个 $j$ 可能是答案。首先，子数组的和应该严格大于 $a_i$ 。另外，该子数组可以合并成一个史莱姆。这种序列存在于两种情况下：

• 子数组的长度为 $1$；
• 子数组中至少有两个不同的值。

如果长度为一，那么子数组中就只有一个史莱姆。如果所有的史莱姆都有相同的大小，那么相邻的两对史莱姆都不能合并，也就是说不可能把所有的史莱姆合并成一个。如果至少有两个不同的值，则存在一对形式为（最大，非最大）的相邻史莱姆。将这样一对史莱姆组合起来后，得到的结果是子数列中唯一的最大值，这意味着它可以吃掉子数列中的所有其他史莱姆。

剩下的问题就是如何找到满足上述条件且尽可能接近 $i$ 的 $j$ （因为所需的运算次数为 $|i-j|$ ），而不是遍历 $j$ 的所有值。我们可以注意到，如果子数组 $[j, i-1]$ 是好的，那么子数组 $[j-1, i-1]$ 也是好的。

因此对于每个 $i$，我们二分 $j$ 并判断。我们还需要预处理 $a$ 的前缀和数组，对于每个 $i$ 离他最近的与他不同的元素位置。

因此，我们可以在 $O(\log{n})$ 中找到一个粘液的答案。总运行时间为 $O(n\log{n})$。

#include <iostream>
#include <set>
#pragma GCC optimize ("Ofast")
#define inf 1000000000
using namespace std;
const int maxn = 300010;
int T, n, a[maxn], f[maxn];
long long s[maxn];
int main () {
  ios::sync_with_stdio (false);
  cin.tie (0);
  cin >> T;
  while (T--) {
    cin >> n;
    for (int i = 1; i <= n; i++) {
      cin >> a[i], s[i] = s[i - 1] + a[i];
      if (a[i] == a[i - 1]) f[i] = f[i - 1];
      else f[i] = i;
    }
    a[0] = a[n + 1] = 0;
    for (int i = 1, l, r, mid, tmp = inf; i <= n; i++) {
      tmp = inf;
      if (a[i + 1] > a[i] || a[i - 1] > a[i]) {cout << 1 << ' '; continue; }
      if (i > 1) {
        l = 1, r = i - 1;
        while (l <= r) {
          mid = l + r >> 1;
          if (s[i - 1] - s[mid - 1] > a[i] && f[i - 1] > mid) l = mid + 1;
          else r = mid - 1;
        }
        int id = l - 1;
        tmp = min (tmp, (id > 0 ? i - id: inf));
      }
      if (i < n) {
        l = i + 1, r = n;
        while (l <= r) {
          mid = l + r >> 1;
          if (s[mid] - s[i] > a[i] && f[mid] > i + 1) r = mid - 1;
          else l = mid + 1;
        }
        int id = r + 1;
        tmp = min (tmp, (id <= n ? id - i: inf));
      }
      cout << (tmp != inf ? tmp : -1) << ' ';
    }
    cout << '\n';
  }
  return 0;
}