题解 | #「LAOI-15」ナイト・オブ・ナイツ# 内测人题解

这是一份 E 题的题解。题解的内容与我内测时的思考过程基本一致，希望能促进读者的理解。

题意

有一个长度为 的序列，每次询问给定一个区间 ，现在每次操作可以让其中一个数除掉一个它自己的质因子，问最少多少次操作可以使得区间内任意相邻两个数都互质。

。

初步分析

区间内任意相邻的两个数都互质，等价于任意相邻的两个数没有相同的质因子。因此对于任意相邻的两个数，我们如果发现了它们有相同的质因子，那么至少有一个数，它的这个质因子必须除干净。

然后可以通过计算得知，，，因此所有数最多只有 个质因子。

想法一

将每个数的 个质因子压成 的状态，代表我这个数保留、删除哪些质因子；同时 表示当前从左到右扫描到第 个位置，状态为 的最小代价。

这样对每个询问进行暴力扫描 DP，时间复杂度是 ，显然 TLE。即使可以数据结构优化也过不了。

想法二（子问题 1）

我们可以先想想只有一个询问的情况如何解决。（即 ）

可以发现不同质因子之间的删除是相互独立的，所以我们可以把每个质因子单独拎出来考虑。对于单个质因子 ，假设序列中所有数分解质因子之后因子 的指数分别是 。那么相当于我们需要清零的 之和要尽量少，并且删后任意相邻两个数 之间至少有一个 。记 代表扫描到第 个数，清零/保留当前的 的最少代价和。

状态转移方程可以写成这样：

当前质因子的答案就是 ，最终将所有质因子的答案相加即可。

这样的时间复杂度是 的，还是太慢了。这时我们再回忆起「所有数最多只有 个质因子」这个结论，就可以知道平均每个质因子里 的位置十分稀疏。所以我们可以优化这个过程，只去扫描 的位置。

当我们从左到右扫描的时候，假设枚举到了 的位置 。我们找到上一个大于零的位置 ，如果 ，那么我们按照上述的方式转移；如果上一个非零的数与当前的数不相邻，那么转移方程就没有任何的限制，变成下面这样子：

这样我们的遍历的总量之和就是 的。至此解决了 的问题。

想法三

接下来我们需要引入「完整段」的概念了。还是以单个质因子 为例，当前 的序列，可以发现如果某个区间 内存在一个 ，那么 的决策与 的决策是互不影响的，满足独立性。

所以我们的 序列可以被等于 的数分割成若干个小段，每个小段内的 均大于 。「完整段」就是每个数都大于 且极长（不能再向两侧延伸）的子区间。记录完整段的原因是，我们可以用想法二的方式预处理每个完整段的答案，并将其储存，这样在给出询问 的时候，我们有办法直接调出所有 内的完整段的答案。由于不同完整段之间是独立的，所以我们可以保证正确性。

如何给定 ，求出所有满足 的完整段 的答案呢？我们可以将询问离线，按照右端点排序。然后右端点扫描到新的位置 的时候，我们加入所有 的完整段 ，查询 的时候只需要找到所有左端点大于 的完整段即可。这可以用树状数组等轻松维护。

然后我们又可以知道，如果一个完整段没有完全包括在询问区间 ，那么它至少会包括 两个端点中的一个。而 分别都最多只有 个质因子，所以我们需要考虑的此类完整段最多只有 种。下面介绍如何专门来求这种未完整包含的完整段。

子问题 2

我们来考虑这个问题：

给定一个序列 ，有 个询问，每个询问给出 ，求区间内需要清零的 之和的最小值，使得删后任意相邻两个数 之间至少有一个 。。

我们记 表示保留区间为 时的最优答案。相邻两个区间 能否合并，取决于 是否至少有一个 。也就是说，同一个区间我们只需要区分左右端点分别清零/保留这四种情况的答案。所以我们对把区间拆成 代表保留区间 ，且清零/保留 ，清零/保留 的最少代价。

具体合并的过程就不多写了，可以参考我写的代码，核心就是相邻的两个数不能同时保留。然后我们就可以线段树来维护标记合并了。

想法三（Cont'd）

至此我们可以将所有没完全包括在询问区间 的完整段，使用子问题 2 的方式去逐一查询。

但是对每一个质因子去开大小为 的序列会爆空间，所以我们可以模仿上面的思路，所有的质因子只保留 非零的位置进行合并。这样序列的长度可以被压成 ，具体实现可以写动态开点线段树，找到每个质因子在序列上对应的左右位置，以及根的编号 。

整合思路

• 将所有数分解质因数，对每个质因子 开一个 vector，记录序列中所有有 这个因子的数的指数。
• 用 DP 预处理所有质因子完整段的答案，并给线段树开点。
• 将询问离线，按右端点升序排序。
• 对每个询问先调出所有完全包含的完整段的答案。
• 然后枚举两个端点 的质因子，用子问题 2（线段树维护）的方式求出没有完全包含的完整段的答案。
• 时间复杂度：。

部分细节

• 注意有涉及完整段的数组均要开到 ，线段树则要更大。
• 如果一个 没有完全包含的完整段 同时包含了 两个端点，只能计入答案一次。
• 可能的常数优化：可以预处理记录每个完整段的前缀答案与后缀答案，这样询问的时候只需要考虑同时覆盖 所有数的完整段。

参考代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 200010, INF = 1e9;

struct P{
    int st, ed, l, r, sum;
}p[N * 6];
struct S{
    int lm, rm, f[2][2];
}s[N * 6 * 4], tmp;
struct Q{
	int l, r, id;
}qr[N];

int n, q, a[N], len[N], id[N][7], seq[N][7], val[N][7], rt[N], L[N * 4* 6], R[N * 4 * 6], t[N], cnt;
vector <int> v[N], w[N];
int ans[N], f[N][2], aa[N * 6], bb[N * 6], st[N * 6], ed[N * 6], nl[N], nr[N], l[N * 6], r[N * 6];

int lb(int x){
	return x & (-x); 
}
void upd(int x, int v){
	for(int i = x; i <= n; i += lb(i))
		t[i] += v;
}
int sum(int x){
	int res = 0;
	for(int i = x; i; i -= lb(i))
		res += t[i];
	return res;
}

// 线段树区间合并

S operator + (S x, S y){
    S z;
    z.lm = x.lm, z.rm = y.rm;
    if(x.rm + 1 != y.lm){
        z.f[0][0] = min(x.f[0][0] + y.f[0][0], min(x.f[0][1] + y.f[0][0], min(x.f[0][0] + y.f[1][0], x.f[0][1] + y.f[1][0])));
        z.f[1][0] = min(x.f[1][0] + y.f[0][0], min(x.f[1][1] + y.f[0][0], min(x.f[1][0] + y.f[1][0], x.f[1][1] + y.f[1][0])));
        z.f[0][1] = min(x.f[0][0] + y.f[0][1], min(x.f[0][1] + y.f[0][1], min(x.f[0][0] + y.f[1][1], x.f[0][1] + y.f[1][1])));
        z.f[1][1] = min(x.f[1][0] + y.f[0][1], min(x.f[1][1] + y.f[0][1], min(x.f[1][0] + y.f[1][1], x.f[1][1] + y.f[1][1])));
    }
    else{
        z.f[0][0] = min(x.f[0][0] + y.f[0][0], min(x.f[0][1] + y.f[0][0], x.f[0][0] + y.f[1][0]));
        z.f[1][0] = min(x.f[1][0] + y.f[0][0], min(x.f[1][1] + y.f[0][0], x.f[1][0] + y.f[1][0]));
        z.f[0][1] = min(x.f[0][0] + y.f[0][1], min(x.f[0][1] + y.f[0][1], x.f[0][0] + y.f[1][1]));
        z.f[1][1] = min(x.f[1][0] + y.f[0][1], min(x.f[1][1] + y.f[0][1], x.f[1][0] + y.f[1][1]));
    }
    return z;
}

void build(int &i, int l, int r){
    if(!i) i = ++cnt;
    if(l == r){
        s[i].lm = s[i].rm = aa[l];
        s[i].f[0][0] = bb[l];
        s[i].f[1][1] = 0;
        s[i].f[0][1] = s[i].f[1][0] = INF;
        return;
    }
    int mid = (l + r) >> 1;
    build(L[i], l, mid), build(R[i], mid + 1, r);
    s[i] = s[L[i]] + s[R[i]];
}

S query(int i, int l, int r, int x, int y){
    if(l >= x && r <= y) return s[i];
    int mid = (l + r) >> 1;
    if(x <= mid && y > mid) return query(L[i], l, mid, x, y) + query(R[i], mid + 1, r, x, y);
    if(x <= mid) return query(L[i], l, mid, x, y);
    if(y > mid) return query(R[i], mid + 1, r, x, y);
    return (S){0, 0, 0, 0, 0, 0};
}

bool cmp(P x, P y){
    return x.ed < y.ed;
}
bool cmp1(Q x, Q y){
	return x.r < y.r;
}

void Main(){
    cin >> n >> q;
    for(int i = 1, x; i <= n; i++){
        cin >> a[i], x = a[i];
        for(int j = 2, ss; j * j <= x; j++) if(x % j == 0){
            ss = 0;
            v[j].push_back(i);
            while(x % j == 0) x /= j, ss++;
            seq[i][++len[i]] = j, val[i][len[i]] = ss;
            w[j].push_back(ss);
        }
        if(x > 1) seq[i][++len[i]] = x, val[i][len[i]] = 1, v[x].push_back(i), w[x].push_back(1);
    }
    int sss = 0;
    int sp = 0;
    
    // 预处理
    for(int i = 1, lenn, ST, ED, tag; i < N; i++) if(v[i].size()){
        lenn = v[i].size();
        for(int j = 0; j < lenn; j++){
            aa[++sss] = v[i][j], bb[sss] = w[i][j];
            if(j == 0 || v[i][j] != v[i][j - 1] + 1){
                ST = v[i][j], tag = sss;
                f[j][0] = w[i][j];
                f[j][1] = 0;
            }
            else{
                f[j][0] = min(f[j - 1][0], f[j - 1][1]) + w[i][j];
                f[j][1] = f[j - 1][0];
            }
            if(j == lenn - 1 || v[i][j] != v[i][j + 1] - 1){
                ED = v[i][j];
                p[++sp] = (P){ST, ED, tag, sss, min(f[j][0], f[j][1])};
            }
        }
        build(rt[i], sss - lenn + 1, sss);
        nl[i] = sss - lenn + 1, nr[i] = sss;
    }
    sort(p + 1, p + sp + 1, cmp);
    for(int i = 1; i <= sp; i++){
        for(int j = p[i].l; j <= p[i].r; j++){
			st[j] = p[i].st, ed[j] = p[i].ed;
			l[j] = p[i].l, r[j] = p[i].r;
		}
	}
	
	sss = 0;
	for(int i = 1; i < N; i++)
		for(int j : v[i]){
			sss++;
			for(int k = 1; k <= len[j]; k++)
				if(seq[j][k] == i)
					id[j][k] = sss;
		}
	for(int i = 1; i <= q; i++)
		cin >> qr[i].l >> qr[i].r, qr[i].id = i;
	sort(qr + 1, qr + q + 1, cmp1);
	
	int nowp = 1, nowq = 1, RES;
	for(int i = 1, A, B; i <= n; i++){
		while(nowp <= sp && p[nowp].ed <= i){
			upd(p[nowp].st, p[nowp].sum);
			nowp++;
		}
		while(nowq <= q && qr[nowq].r <= i){
			RES = sum(n) - sum(qr[nowq].l - 1);
			A = qr[nowq].l, B = qr[nowq].r;
            
			for(int j = 1, ID; j <= len[A]; j++)
				if(st[id[A][j]] < A){
					if(ed[id[A][j]] > B){
						for(int k = 1; k <= len[B]; k++)
							if(seq[B][k] == seq[A][j]){
								ID = id[B][k];
								break;
							}
					}
					else ID = r[id[A][j]];
					tmp = query(rt[seq[A][j]], nl[seq[A][j]], nr[seq[A][j]], id[A][j], ID);
					RES += min(tmp.f[0][0], min(tmp.f[0][1], min(tmp.f[1][0], tmp.f[1][1])));
				}
			
			for(int j = 1, ID; j <= len[B]; j++){
				if(ed[id[B][j]] > B){
					if(st[id[B][j]] >= A){
						ID = l[id[B][j]];
					
						tmp = query(rt[seq[B][j]], nl[seq[B][j]], nr[seq[B][j]], ID, id[B][j]);
						RES += min(tmp.f[0][0], min(tmp.f[0][1], min(tmp.f[1][0], tmp.f[1][1])));
					}
				}
			}
			ans[qr[nowq].id] = RES;
			nowq++;
		}
	}
	
	for(int i = 1; i <= q; i++)
		cout << ans[i] << endl;
}

signed main(){
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	int _T = 1;
// 	cin >> _T;
	while(_T--) Main();
	
	return 0;
}