CF1516D 不互素区间划分 - 倍增/分块维护跳链

· · 题解

根号暴力吊打 \log
划分在一个区间内的数要求两两互质
比较容易求出每一个数下一个与它不互素的数:
1) 预处理出素数和最小质因子, 可以在 \log 的时间分解质因数。
2) 倒顺枚举 , 记录每个素数作为因子最早出现的位置。分解当前数时将每个素因子最早出现的位置取 \min

考虑暴力怎么做。给定一个固定的询问区间 , 从左到右贪心选择最靠右的端点满足题意。记从 x 位置开始的最大区间右端点 +1 为 f(x) , 每个数右边第一个与它不互素的数为 p(x)。
则有:

f(x) = \min\{f(x+1) , p(x)\}

这个可以 \mathcal{O(n)} 求。
如果要预处理出所有 g(x,y) 表示 x 到 y 的段数状态数是 \mathcal{O(n^2)} 的。
借助 f(x) 暴力跳很容易单次卡到 \mathcal{O(n)}。
这个借助 f(x) 暴力跳的过程非常类似在树上跳链, 很容易想到倍增优化。
当然考场犯浑选手想的是分块维护跳的过程, 还写挂了。
需要维护两个值, nstp(x) 表示 x 跳出所在块需要的步数, nexb(x) 表示跳出所在块后跳到的节点。这两个值很容易用 f(x) 非常快地求出来。
然后就是经典的跳法了, 不在同一块就整块跳过, 在同一块就一步步跳, 理论上一次查询复杂度是 \mathcal(\sqrt n) 的。
然而跑得飞快, 基本上吊打倍增写法。 

#include <iostream>
#include <cmath>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)

using namespace std;

const int maxn = 1e5+10;
int Prime[maxn], vp[maxn], minf[maxn], tot;
void seive(int n) {
    minf[1] = 1;
    rep(i,2,n) {
        if(!vp[i]) vp[i] = 1, Prime[++tot] = i, minf[i] = i;
        for(int j = 1; 1ll * i * Prime[j] <= n; ++j) {
            vp[i*Prime[j]] = 1, minf[i*Prime[j]] = Prime[j];
            if(i % Prime[j] == 0) break;
        }
    }
}

#define gb(x) ((x-1)/blk+1)
#define hob(x) ((x-1)*blk+1)
#define eob(x) (min(n,(x)*blk))
int a[maxn], n;
int lp[maxn], nex[maxn];
int nstp[maxn], nxp[maxn], blk;
void prework() {
    blk =  min(n, (int)sqrt(n)+1);
    rep(i,1,1e5) lp[i] = n + 1; rep(i,1,n+1) nex[i] = n + 1;
    seive(1e5);
    per(i,n,1) {
        int m = a[i]; nex[i] = nex[i+1];
        while(m != 1) {
            int t = minf[m];
            while(m % t == 0) m /= t;
            nex[i] = min(nex[i], lp[t]); lp[t] = i;
        }
    }
    per(i,n,1) {
        nex[i] <= eob(gb(i)) ?
            (nstp[i] = nstp[nex[i]] + 1, nxp[i] = nxp[nex[i]]) :
            (nstp[i] = 1, nxp[i] = nex[i]);
    }
}

int main() {
    if(fopen("yl.in", "r")) {
        freopen("yl.in", "r", stdin);
        freopen("yl.out", "w", stdout);
    }
    int q; scanf("%d %d", &n, &q);
    rep(i,1,n) scanf("%d", a + i);
    prework();
    int l, r;
    rep(qr,1,q) {
        int ans = 0;
        scanf("%d %d", &l, &r);
        while(gb(l) < gb(r)) ans += nstp[l], l = nxp[l];
        while(l <= r) ++ans, l = nex[l];
        printf("%d\n", ans);
    }
    return 0;
}