「COCI2024-2025#5」塔楼 / Tornjevi

题目描述

给定正整数序列 $h_1,\ldots,h_n$。

对于区间 $[l,r]$，我们称 $i$（$l\le i\le r$）关于 $[l,r]$ 是 ，当且仅当：。

对于 $i$，定义 $f(i)$ 表示：所有 $i$ 关于 $[l,r]$ 是好的区间中，$r-l+1$ 的最大值。

对于 $i=1,2,\ldots,n$，求出 $f(i)$。

$n \le 10^6$

题目分析

利用 ST 表我们可以做到以 $O(1)$ 的代价查询区间最大公约数。

现在，我们考虑区间 $[i, r]$ 的区间元素最大公约数是 $h_i$，$r$ 的最大值。$r$ 显然具有单调性，可以二分求出 $$ 的最大值。同理可求得区间 中 的最小值。

时间复杂度 $O(n\log n)$

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

const int N = 1e6 + 10;
int n, h[N];
int f[N][20];

int query(int x, int y) {
  int k = log(y - x + 1) / log(2);
  return __gcd(f[x][k], f[y - (1 << k) + 1][k]);
}

int main() {
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> h[i];
    f[i][0] = h[i];
  }
  
  // 预处理 ST 表
  int t = log(n) / log(2) + 1;
  for (int k = 1; k <= t; k++) {
    for (int i = 1; i <= n - (1 << k) + 1; i++) {
      f[i][k] = __gcd(f[i][k - 1], f[i + (1 << k - 1)][k - 1]);
    }
  }

  for (int i = 1; i <= n; i++) {
    int a = , b = i;
     (a < b) {
       mid = a + b >> ;
       ((mid, i) < h[i]) a = mid + ;
       b = mid;
    }
     l = a;
    a = i, b = n;
     (a < b) {
       mid = a + b +  >> ;
       ((i, mid) < h[i]) b = mid - ;
       a = mid;
    }
     r = b;
    cout << r - l +  << ;
  }
}