[COCI 2024/2025 #5] 塔楼 / Tornjevi 题解

FFTotoro · 2025-02-20 10:33:48 · 题解

枚举 i，跟据 \gcd 的性质（\gcd\limits_{j=l}^r h_j=\gcd\left(\gcd\limits_{j=l}^i h_j,\gcd\limits_{j=i}^r h_j\right)），且区间 \gcd 具有单调性，只需要向左 / 右分别二分出最小的满足 \gcd\limits_{j=l}^i h_j=h_i 的 l 和最大的满足 \gcd\limits_{j=i}^r h_j=h_i 的 r 即可。查询区间 \gcd 可以使用 ST 表维护。时间复杂度 O(n\log n\log\max\{h_i\})。

放代码：

#include<bits/stdc++.h>
using namespace std;
namespace IAOI_lib{
  template<typename T,T(*op)(T,T)> class sparse_table{
    private:
      vector<vector<T> > s;
    public:
      sparse_table(vector<T> a){
        int k=__lg(a.size());
        s.resize(a.size(),vector<T>(k+1));
        for(int i=0;i<a.size();i++)
          s[i][0]=a[i];
        for(int i=1;i<=k;i++)
          for(int j=0;j+(1<<i)<=a.size();j++)
            s[j][i]=op(s[j][i-1],s[j+(1<<i-1)][i-1]);
      }
      inline T query(int l,int r){
        int k=__lg(r-l+1);
        return op(s[l][k],s[r-(1<<k)+1][k]);
      }
  }; // ST 表维护区间 gcd
}
int main(){
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  int n; cin>>n;
  vector<int> h(n);
  for(auto &i:h)cin>>i;
  IAOI_lib::sparse_table<int,gcd> s(h);
  for(int i=0;i<n;i++){
    int L=0,R=i,x=-1;
    while(L<R){
      int m=L+R>>1;
      if(s.query(m,i)<h[i])L=m+1;
      else R=m;
    } // 二分找左端点
    x=R,L=i,R=n-1;
    while(L<R){
      int m=L+R+1>>1;
      if(s.query(i,m)<h[i])R=m-1;
      else L=m;
    } // 二分找右端点
    cout<<L-x+1<<' ';
  }
  cout<<endl;
  return 0;
}