Re代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
constexpr int maxn = 2e5 + 5;
int L[maxn];
int dp[maxn][20];
int o[maxn];
inline int count(int l, int r)
{
  int s = L[r - l + 1];
  return gcd(dp[l][s], dp[r - (1 << s) + 1][s]);
}
signed main()
{
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  vector<pair<int, int>> ans;
  L[1] = 0;
  for (int i = 2; i < maxn; i ++) L[i] = L[i / 2] + 1;
  int n; cin >> n;
  vector<int> a(n); 
  for (int i = 0; i < n; i ++) 
  {
    cin >> a[i];
    dp[i + 1][0] = a[i];
  }
  for (int j = 1; j <= 17; j ++)
  {
    for (int i = 1; i <= n; i ++)
    {
      if ((i + (1 << j) - 1) <= n) 
      {
                dp[i][j] = gcd(dp[i][j - 1], dp[i + (1 << (j - 1))][j - 1]);
      }
    }
  }
  for (int i = 1; i <= n; i ++)
  {
        if (count(i, n) > n - i + 1) continue;
        int l = i, r = n;
        while (l + 1 < r) 
    {
            int mid = (l + r) / 2;
            if (count(i, mid) <= mid - i + 1) r = mid;
      else l = mid + 1;
        }

        int pos = 0;
        if (count(i, l) <= l - i + 1) pos = l;
        else pos = r;

        if (pos - i + 1 == count(i, pos)) ans.emplace_back(i, pos);
    }

    sort(ans.begin(), ans.end());

    int S = ans.size();


    int now = 0, i = 0;
    while (true)
  {
        now = ans[i].second;
        int j = i;

        while (j + 1 < S && ans[j + 1].first <= now) j ++;

        o[now] ++;
        i = j + 1;
        if (i >= S) break;
    }

    for (int i = 1; i <= n; i ++) 
  {
        o[i] += o[i - 1];
        printf("%d ", o[i]);    
    }

  return 0;
}

下面这个是AC代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
constexpr int maxn = 2e5 + 5;
int L[maxn];
int dp[maxn][20];
int o[maxn];
inline int count(int l, int r)
{
  int s = L[r - l + 1];
  return gcd(dp[l][s], dp[r - (1 << s) + 1][s]);
}
signed main()
{
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  vector<pair<int, int>> ans;
  L[1] = 0;
  for (int i = 2; i < maxn; i ++) L[i] = L[i / 2] + 1;
  int n; cin >> n;
  vector<int> a(n); 
  for (int i = 0; i < n; i ++) 
  {
    cin >> a[i];
    dp[i + 1][0] = a[i];
  }
  for (int j = 1; j <= 17; j ++)
  {
    for (int i = 1; i <= n; i ++)
    {
      if ((i + (1 << j) - 1) <= n) 
      {
                dp[i][j] = gcd(dp[i][j - 1], dp[i + (1 << (j - 1))][j - 1]);
      }
    }
  }
  for (int i = 1; i <= n; i ++)
  {
        if (count(i, n) > n - i + 1) continue;
        int l = i, r = n;
        while (l + 1 < r) 
    {
            int mid = (l + r) / 2;
            if (count(i, mid) <= mid - i + 1) r = mid;
      else l = mid + 1;
        }

        int pos = 0;
        if (count(i, l) <= l - i + 1) pos = l;
        else pos = r;

        if (pos - i + 1 == count(i, pos)) ans.emplace_back(i, pos);
    }

    sort(ans.begin(), ans.end());

    int S = ans.size();


    int now = 0, i = 0;
    while (true)
  {
        if (i >= S) break;
        now = ans[i].second;
        int j = i;

        while (j + 1 < S && ans[j + 1].first <= now) j ++;

        o[now] ++;
        i = j + 1;
    }

    for (int i = 1; i <= n; i ++) 
  {
        o[i] += o[i - 1];
        printf("%d ", o[i]);    
    }

  return 0;
}