P5629 【AFOI-19】区间与除法 题解

· · 题解

为什么题解全是状压 ST 表什么的捏。

来一个前缀和题解。

Part 1：处理原数

设 b 数组存储的是这 m 个原数。

原数可能会有重复（比如样例 1），所以先把 b 去重。由于 m 很小所以可以暴力 \operatorname{O}(m^2) 实现。

注意到每个原数也可能可以被其他原数消灭，设 b_i 可以被 b_j 消灭（i \ne j）。

每个能被 b_i 消灭的数，由于其被除到 b_i 后一定能被除到 b_j，所以一定也能被 b_j 消灭。

有结论：若 x 能被 y 消灭且 y 能被 z 消灭，则 x 能被 z 消灭。

当 b_i 可以被 b_j 消灭时，b_i 可以消灭的数集 是 b_j 可以消灭的数集 的子集。于是 b_i 就能被 b_j 代替。

所以我们二次处理 b 数组，对所有 b_i，如果能找到一个可以消灭 b_i 的 b_j（i \ne j），则删去 b_i。

处理过后，每个 a_i 只能被 0 或 1 个原数消灭，\operatorname{O}(m\log a_i) 求出这个原数 c_i（因为 d 的值有变等原因并跑不满）。

这一部分总复杂度 \operatorname{O}(m^2+m^2\log V+mn\log V) = \operatorname{O}(mn\log V) （V 为 a_i,b_i 上界）。

Part 2：处理询问

经过 \text{Part 1} 的处理，得到了 c 数组，而询问就变成了区间数颜色，并且颜色数 \leq60。

则有一个显然的做法：枚举每个原数，判断区间中原数是否存在，存在则答案加一。

可以先前缀和一遍，sum_{i,j} 表示 c 的前 i 个元素中第 j 个原数出现的次数。然后 \operatorname{O}(1) 实现判断区间中原数是否存在。

最后输出答案即可。

这一部分复杂度为 \operatorname{O}(qm)。

坑点：

AC代码：


// Problem: P5629 【AFOI-19】区间与除法
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P5629
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// Powered by CP Editor (https://cpeditor.org)
// Auther: Sugar_Pigeon(227728)

#include <bits/stdc++.h>
using namespace std;
#define M 1000006
#define INT long long
INT n,m,ox,oy,nm,d,q,a[M],nd[M],b[M],ans,c[M],hav0;
int sum[M][65];
void calc(INT x) {
    INT y=a[x];
    if(hav0) {nd[x]=0;return;}
    while(y) {
        for(INT i=1;i<=m;i++) {
            if(b[i]==y) {
                nd[x]=y;
                return;
            }
        }
        y/=d;
    }
    if(!nd[x]) nd[x]=-1;
    return;
}
bool dop(INT x) {
    while(x)
    {
        x/=d;
        for(INT i=1;i<=m;i++)
            if(b[i]==x)
                return 1;
    }
    return 0;
}
signed main() {
    scanf("%lld%lld%lld%lld",&n,&m,&d,&q);
    for(INT i=1;i<=n;i++)
        scanf("%lld",&a[i]);
    for(INT i=1;i<=m;i++) {
        scanf("%lld",&b[i]);
        for(INT j=1;j<i;j++) {
            if(b[j]==b[i]) {
                m--,i--;
                break;
            }
        }
    }
    sort(b+1,b+m+1);
    for(INT i=m;i>=1;i--) {
        if(!dop(b[i])) {
            c[++nm]=b[i];
        }
    }
    m=nm;
    for(INT i=1;i<=m;i++)
        b[i]=c[i],hav0=((hav0||!b[i])?1:0);
    for(INT i=1;i<=n;i++)
        calc(i);
    for(INT i=1;i<=n;i++)
        for(INT j=1;j<=m;j++)
            sum[i][j]=sum[i-1][j]+(nd[i]==b[j]?1:0);
    for(INT Q=1;Q<=q;Q++) {
        scanf("%lld%lld",&ox,&oy);
        ans=0;
        for(INT i=1;i<=m;i++)
            if(sum[oy][i]-sum[ox-1][i])
                ans++;
        printf("%lld\n",ans);
    }
    return 0;
}