Codeforces Round #769 (Div. 2) - D. New Year Concert

GCD + st表 + 二分

题意

给出一个长度为 \(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 个数组成的数组修改好的最小操作次数

思路

每次最优的修改是把当前的数改为一个极大的质数，这样包含这个数的区间肯定都是合法的
记上一次修改的位置是 L，对于每一个右端点 r，从 L + 1 到 r 枚举左端点，逐个判断 \([l,r]\) 是否合法，有不合法的就把 \(a[r]\) 改为大质数并更新 L
上述策略是 \(O(n^2)\) 的，但固定右端点，枚举左端点的过程是有单调性的，因为随着区间长度变小，区间gcd变大，因此可以二分找到

区间gcd == 区间长度的位置
区间gcd用st表预处理出

#include <bits/stdc++.h>

using namespace std;

#define endl "\n"

typedef long long ll;

typedef pair<int, int> PII;

const int N = 2e5 + 10;

int n;

int a[N];

template<typename T> 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<vector<T>> 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<int> 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;

}

巴特西

Codeforces Round #769 (Div. 2) - D. New Year Concert

GCD + st表 + 二分

题意

思路

最新文章

热门文章