【题解】CF1732E-分块

· · 题解

警告&题外话

赛时看都没看这道题，赛后看感觉还行。

（虽然这题我两个小时写不完，TLE十几次）

此题偏难，代码难度较大（对于我的方法），建议评黑，不建议没做完 数列分块入门九道 的人做，因为不会讲分块基本操作。

如果有更好方法的不要嘲讽我。

如果发现我方法正确性与时空复杂度有误的请私聊。（免得丢脸）

题意

见翻译。

思路

分析操作的可实现性和数据范围，凭借做题经验，我们可以初步估计此题采用分块是最合适的。

Codeforces 评论区中也有更快的做法，好像是线段树，我也想讲，可惜我不会。

如何分块？我们会发现根据题目要求，对于分块中整体处理的块，我们必须 O(1) 解决，但修改操作是区间赋值，怎么办？

1 \leq x,a_i,b_i \leq 5 \cdot 10^4

实际上，此题的值域全是 5\times 10^4，设 W 表示 a_i 的最大取值，则遍历全体整数可能值与所有块的总时间复杂度可表示为 O(W \cdot \sqrt{n})，而不会超时。

这个条件给了我们启发——如果可以将每个块中整体赋给 a_i 每种可能值时整个块查询的最小值预处理出来，那么就可以对分块中整体处理的块 O(1) 解决。

这又如何做？

首先，此题求：

\min\limits_{i \in [l,r]}\frac{\operatorname{lcm}(a_i,b_i)}{\gcd(a_i,b_i)}

我们会发现把分母从 \gcd(a_i,b_i) 换成 a_i,b_i 的任何一个公因数然后取 \min，那么最小的结果仍然是 \frac{\operatorname{lcm}(a_i,b_i)}{\gcd(a_i,b_i)}。

所以我们尝试先走弯路，考虑枚举一个块中所有 b_i 的所有因子，将其存入一个大小为 5 \times 10 ^ 4 的有序数对桶中（因子为下标，（b_i/ 因子，因子）成为有序数对作为其中值），然后用类似线性筛的思路向上找倍数对其关于自身的有序数对取 \min 更新桶中当前值，大小比较的方式为：

对于两个有序数对 (A,B)(C,D)

若满足：\frac{A}{B} \leq \frac{C}{D}

即：A \cdot D \leq B \cdot C

则称 (A,B) \leq (C,D)

认真思考，对于一个更新完毕的有序数对桶：

ton_{first/second}

计算对于一个可能的整数 i 赋值给整个块的 a_i，那么此时整个块查询的最大值即为：

\frac{i \cdot ton_{i_{first}}}{ton_{i_{second}}}

由此，我们将每个块中整体赋给 a_i 每种可能值时整个块查询的最大值预处理出来了，设 W 表示 a_i 最大取值，则单块时间复杂度 O(W + \log_{2}{n} \cdot \sqrt{n})。

所以预处理总时间复杂度 O(W \cdot \sqrt{n} + n \cdot \log_{2}{n})，剩下的就是分块基本操作，如果不会可以先练数列分块入门九道 。

（推销博客中）

此题常数较大，建议加：

火车头，超级快读，快输，以及其他卡常技艺。

代码

//火车头略
#include <bits/stdc++.h>
#include <immintrin.h>
using namespace std;
#define int unsigned int
int n, Q, a[50005], b[50005], Typ, L, R, X, prime[50005], cnt;
int sq, len, block[50005], bl[505], br[505], bmin[505], bcg[505], bres[505][50005], pl;
long long minn[50005], tlp[50005];
bool ton[50005], not_prime[50005];
vector < int > fac[50005];
static char buf[1000000], * p1 = buf, * p2 = buf;
#define getchar() p1 == p2 && (p2 = (p1 = buf) + fread (buf, 1, 1000000, stdin), p1 == p2) ? EOF : * p1 ++
inline int read()
{
    register int x = 0;
    register char c = getchar ();
    while (c < '0' || c > '9') c = getchar ();
    while (c >= '0' && c <= '9') x = (x << 1) + (x << 3) + (c ^ 48),c = getchar ();
    return x;
}
void inline print (register int a){
    if (a < 0){
        putchar ('-');
        a = - a;
    }
    if (a < 10)
        putchar (a ^ 48);
    else {
        print (a / 10);
        putchar ((a % 10) ^ 48);
    }
}
inline int gcd (register int i, register int j){
    if (j == 0)
        return i;
    return gcd (j, i % j);
}
void inline push_d (register int i){
    if (bcg[i]){
        for (register int j = bl[i];j <= br[i];++ j)
            a[j] = bcg[i];
        bcg[i] = 0;
    }
}
void inline push_u (register int i){
    bmin[i] = INT_MAX;
    for (register int j = bl[i];j <= br[i];++ j){
        pl = gcd (a[j], b[j]);
        bmin[i] = min (bmin[i], a[j] / pl * b[j] / pl);
    }
}
void inline Build (){
    len = 100;
    sq = n / len;
    while (sq * len < n)
        ++ sq;
    for (register int i = 1;i <= sq;++ i){
        for (register int j = 1;j <= 5e4;++ j){
            minn[j] = 5e9;
            tlp[j] = j;
            ton[j] = false;
        }
        bl[i] = br[i - 1] + 1;
        br[i] = min (n, bl[i] + len - 1);
        push_u (i);
        for (register int j = bl[i];j <= br[i];++ j){
            block[j] = i;
            if (! ton[b[j]]){
                ton[b[j]] = true;
                for (register int k = 0;k < (int) fac[b[j]].size ();++ k)
                    minn[fac[b[j]][k]] = min (minn[fac[b[j]][k]], 1ll * b[j] / fac[b[j]][k]);
            }
        }
        for (register int j = 1;j <= 5e4;++ j){
            bres[i][j] = j / tlp[j] * minn[j];
            for (register int k = 1;k <= cnt && j * prime[k] <= 5e4;++ k)
                if (1ll * minn[j * prime[k]] * tlp[j] > 1ll * minn[j] * tlp[j * prime[k]]){
                    minn[j * prime[k]] = minn[j];
                    tlp[j * prime[k]] = tlp[j];
                }
        }
    }
}
void inline Update (register int l, register int r, register int x){
    push_d (block[l]);
    for (register int i = l;i <= min (br[block[l]], r);++ i)
        a[i] = x;
    push_u (block[l]);
    for (register int i = block[l] + 1;i < block[r];++ i){
        bcg[i] = x;
        bmin[i] = bres[i][x];
    }
    if (block[l] == block[r])
        return ;
    push_d (block[r]);
    for (register int i = bl[block[r]];i <= r;++ i)
        a[i] = x;
    push_u (block[r]);
}
inline int Query (register int l, register int r){
    register int Ans = INT_MAX * 2ll - 1;
    push_d (block[l]);
    for (register int i = l;i <= min (br[block[l]], r);++ i){
        pl = gcd (a[i], b[i]);
        Ans = min (Ans, a[i] / pl * b[i] / pl);
    }
    for (register int i = block[l] + 1;i < block[r];++ i)
        Ans = min (Ans, bmin[i]);
    if (block[l] == block[r])
        return Ans;
    push_d (block[r]);
    for (register int i = bl[block[r]];i <= r;++ i){
        pl = gcd (a[i], b[i]);
        Ans = min (Ans, a[i] / pl * b[i] / pl);
    }
    return Ans;
}
signed main (){
    for (register int i = 1;i <= 5e4;++ i){
        if (! not_prime[i])
            prime[++ cnt] = i;
        for (register int j = 1;i * j <= 5e4;++ j){
            if (i != 1)
                not_prime[i * j] = true;
            fac[i * j].push_back (i);
        }
    }
    n = read ();
    Q = read ();
    for (register int i = 1;i <= n;++ i)
        a[i] = read ();
    for (register int i = 1;i <= n;++ i)
        b[i] = read ();
    Build ();
    while (Q --){
        Typ = read ();
        L = read ();
        R = read ();
        if (Typ == 1){
            X = read ();
            Update (L, R, X);
        }
        if (Typ == 2){
            print (Query (L, R));
            putchar ('\n');
        }
    }
    return 0;
}