Problem - 1632D - Codeforces

题意

给出一个长度为 \(n\;(1<=n<=2*10^5)\) 的数组 \(a[i]\;(1<=a[i]<=10^9)\), 可以修改任何一个位置的数为任何一个正整数，对于任意一段区间 \([l,r]\;(1<=l<=r<=n)\)，不能出现 \(gcd(a[l],a[l+1],…,a[r])=r-l+1\)

对于每个 \(i(1<=i<=n)\) , 求把前 i 个数组成的数组修改好的最小操作次数

思路

1. 每次最优的修改是把当前的数改为一个极大的质数，这样包含这个数的区间肯定都是合法的

2. 记上一次修改的位置是 L，对于每一个右端点 r，从 L + 1 到 r 枚举左端点，逐个判断 \([l,r]\) 是否合法，有不合法的就把 \(a[r]\) 改为大质数并更新 L

3. 上述策略是 \(O(n^2)\) 的，但固定右端点，枚举左端点的过程是有单调性的，因为随着区间长度变小，区间gcd变大，因此可以二分找到

   区间gcd == 区间长度的位置

4. 区间gcd用st表预处理出

   #include
   using namespace std;
   #define endl "\n"

   typedef long long ll;
   typedef pair PII;

   const int N = 2e5 + 10;
   int n;
   int a[N];
   template struct ST
   {
   ST(T a[], int n){
   siz = n;
   g.resize(n+1);
   int t = __lg(n) + 1;
   for(int i=1;i<=n;i++) g[i].resize(t);

       for(int i = 1; i <= n; i++) g[i][0] = a[i];
       for(int j = 1; j < t; j++)
       {
           for(int i = 1; i <= n - (1<<j)+1; i++)
           {
               g[i][j] = __gcd(g[i][j-1], g[i+(1 << (j-1))][j-1]);
           }
       }
   }
   T get_gcd(int l,int r)
   {
       int k = __lg(r-l+1);
       return __gcd(g[l][k], g[r-(1<<k)+1][k]);
   }

   private:
   int siz = 0;
   vector> g;
   };

   int main()
   {
   ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
   cin >> n;
   for (int i = 1; i <= n; i++) cin >> a[i];
   ST st(a, n);
   int cnt = 0;
   int L = 0;
   for (int i = 1; i <= n; i++) { int l = L, r = i; while(l + 1 != r) { int mid = l + r >> 1;
   if (st.get_gcd(mid, i) >= i - mid + 1)
   r = mid;
   else
   l = mid;
   }
   int tmp = st.get_gcd(r, i);
   if (tmp == i - r + 1)
   {
   cnt++;
   L = i;
   }
   cout << cnt << " ";
   }
   cout << endl;
   return 0;
   }