CF1732E

算法复健ing

原题链接:https://codeforces.com/contest/1732/problem/E

大意:给定长度为n的数组a与b,有两种操作,为a区间赋值x,区间最值查询,需要维护的是a[i]*b[i]/gcd(a[i],b[i])/gcd(a[i],b[i])的最值

题解:

先从暴力入手,暴力修改,暴力询问,时间复杂度为O(qN),时间复杂度为O(3e9*log)

但注意,区间赋值时,赋的值都是相同的,故容易联想到分块操作,离散块暴力修改,区间块使用tag修改

假设块长为k,则我们获得了n/k个块,接下来考虑如何维护对各个块的询问

对于离散块,暴力修改,并记录修改后的值是否为最值

由于能赋的值范围较小,对于整块,我们对每个块维护一个ans[k],为当前块都被赋成k值时,当前块的答案.

对于给定的k,我们遍历k的所有约数,对于所有约数,寻找最小的b[i],能被该约数整除(即先假定该约数是gcd,当gcd一定时,b[i]越小,其代表的答案越小),遍历所有的约数后,记录最小答案的位置为i

证明该最小答案的正确性:假设k的两个约数d1,d2均能整除某个b[i],则其中较大者一定是更优答案,且一定会被遍历到.即最终取得的一定是最优情况

这里写法有个小trick,直接for(int i=1;i<=MAX;i++),约数放在外面,然后for(int k=i;k<=MAX;k+=i),复杂度为MAX(logMAX);同时用个vis数组标记当前块中是否存在b[i]=k,若存在,则直接取符合条件的最小的b[i]去更新答案

#include <bits/stdc++.h>
using namespace std;
using ll = int64_t;
/*head*/

#define fi first
#define se second
#define rep(i, a, b) for (ll i = (a); i < (b); i++)
#define sz(x) ((ll)x.size())
//#define DE_BUG
/*define*/
const ll maxn = 5e4 + 10;
const ll max2 = 3e2 + 10;
const ll INF = 1e18;
ll T, n, m, k, q, sq;
ll L[max2], R[max2];
ll mn[max2];
ll lazy[max2];
ll id[maxn];
ll p[max2][maxn];
bool vis[maxn];
ll a[maxn], b[maxn];
inline ll read()
{
    ll s = 0;
    char ch = getchar();
    while (ch < '0' || ch > '9')
    {
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        s = s * 10 + ch - '0';
        ch = getchar();
    }
    return s;
}

inline void write(ll x)
{

    if (x > 9)
        write(x / 10);
    putchar(x % 10 + '0');
}
ll gcd(ll a, ll b)
{
    ll A = __builtin_ctz(a), B = __builtin_ctz(b), k = min(A, B);
    b >>= B;
    while (a)
    {
        a >>= A;
        ll c = b - a;
        A = __builtin_ctz(c);
        b = min(a, b), a = abs(c);
    }
    return b << k;
}
void init(ll n)
{
    sq = sqrt(n);
    R[0] = 0;
    for (ll i = 1; i <= sq; i++)
    {
        L[i] = R[i - 1] + 1;
        R[i] = i * sq;
        for (ll j = L[i]; j <= R[i]; j++)
        {
            id[j] = i;
        }
    }
    if (R[sq] < n)
    {
        sq++;
        R[sq] = n, L[sq] = R[sq - 1] + 1;
        for (ll j = L[sq]; j <= R[sq]; j++)
        {
            id[j] = sq;
        }
    }
}
void pre()
{
    for (ll i = 1; i <= sq; i++)
    {
        lazy[i] = 0;
        mn[i] = INF;
        for (ll j = 1; j < maxn; j++)
        {
            p[i][j] = INF;
        }
    }
    for (ll i = 1, tmp, d; i <= n; i++)
    {
        d = gcd(a[i], b[i]);
        tmp = a[i] / d * b[i] / d;
        mn[id[i]] = min(mn[id[i]], tmp);
    }
    for (ll i = 1; i <= sq; i++)
    {
        for (ll j = L[i]; j <= R[i]; j++)
        {
            vis[b[j]] = 1;
        }
        for (ll j = 1, tmp; j < maxn; j++)
        {
            tmp = 0; //找到最小的b[i]
            for (ll k = j; k < maxn; k += j)
            {
                if (vis[k])
                {
                    tmp = k;
                    break;
                }
            }
            if (!tmp)
            {
                continue;
            }
            for (ll k = j; k < maxn; k += j)
            {
                p[i][k] = min(p[i][k], k / j * tmp / j);
            }
        }
        for (ll j = L[i]; j <= R[i]; j++)
        {
            vis[b[j]] = 0;
        }
    }
}
void up(ll u)
{
    mn[u] = INF;
    for (ll i = L[u], tmp, d; i <= R[u]; i++)
    {
        d = gcd(a[i], b[i]);
        tmp = a[i] / d * b[i] / d;
        mn[u] = min(mn[u], tmp);
    }
}
void update(ll l, ll r, ll val)
{
    ll u = id[l], v = id[r];
    if (u == v)
    {
        if (lazy[u])
        {
            for (ll i = L[u]; i <= R[u]; i++)
            {
                if (i >= l && i <= r)
                {
                    a[i] = val;
                }
                else
                {
                    a[i] = lazy[u];
                }
            }
            lazy[u] = 0;
        }
        else
        {
            for (ll i = l; i <= r; i++)
            {
                a[i] = val;
            }
        }
        up(u);
        return;
    }
    else
    {
        if (lazy[v])
        {
            for (ll i = L[v]; i <= R[v]; i++)
            {
                if (i >= l && i <= r)
                {
                    a[i] = val;
                }
                else
                {
                    a[i] = lazy[v];
                }
            }
            lazy[v] = 0;
        }
        else
        {
            for (ll i = L[v]; i <= r; i++)
            {
                a[i] = val;
            }
        }
        if (lazy[u])
        {
            for (ll i = L[u]; i <= R[u]; i++)
            {
                if (i >= l && i <= r)
                {
                    a[i] = val;
                }
                else
                {
                    a[i] = lazy[u];
                }
            }
            lazy[u] = 0;
        }
        else
        {
            for (ll i = l; i <= R[u]; i++)
            {
                a[i] = val;
            }
        }
        up(u), up(v);
        for (ll i = u + 1; i < v; i++)
        {
            lazy[i] = val;
            mn[i] = p[i][val];
        }
    }
}
ll query(ll l, ll r)
{
    ll u = id[l], v = id[r];
    ll ret = INF;
    if (u == v)
    {
        for (ll i = l, tmp, d; i <= r; i++)
        {
            if (lazy[u])
            {
                a[i] = lazy[u];
            }
            d = gcd(a[i], b[i]);
            tmp = a[i] / d * b[i] / d;
            ret = min(tmp, ret);
        }
        return ret;
    }
    else
    {
        for (ll i = l, tmp, d; i <= R[u]; i++)
        {
            if (lazy[u])
            {
                a[i] = lazy[u];
            }
            d = gcd(a[i], b[i]);
            tmp = a[i] / d * b[i] / d;
            ret = min(tmp, ret);
        }
        for (ll i = L[v], tmp, d; i <= r; i++)
        {
            if (lazy[v])
            {
                a[i] = lazy[v];
            }
            d = gcd(a[i], b[i]);
            tmp = a[i] / d * b[i] / d;
            ret = min(tmp, ret);
        }
        for (ll i = u + 1; i < v; i++)
        {
            ret = min(ret, mn[i]);
        }
        return ret;
    }
}
void solve()
{
    cin >> n >> q;
    for (ll i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    for (ll i = 1; i <= n; i++)
    {
        cin >> b[i];
    }
    init(n);
    pre();
    for (ll i = 1, t, l, r, x; i <= q; i++)
    {
        cin >> t >> l >> r;
        if (t == 1)
        {
            cin >> x;
            update(l, r, x);
        }
        else
        {
            cout << query(l, r) << "\n";
        }
    }
}

int main()
{
    T = 1;
    cin.tie(0);
    ios::sync_with_stdio(false);
    // cin >> T;
    while (T--)
    {
        solve();
    }
    return 0;
}

注意:用了nb版本的gcd,否则狂T

两种gcd时间对比