题解：P16177 [ICPC 2014 NAIPC] Fantastic Problem

· · 题解

题意简述

维护一个数列。每次单点修改后，求有多少个长度为 k 的连续子段不满足两两互质。最后输出修改结束时的数列元素和。

解题思路

两个数不互质，当且仅当它们包含相同的质因数。先预处理每个数的所有不同质因数，并为每个质数维护它整除的元素位置集合。

对每个位置 i，定义 r_i 为右侧第一个与 a_i 不互质的位置。若该位置不存在，则令 r_i=n+1。枚举 a_i 的质因数，并在对应集合中查询 i 的后继，取所有后继的最小值即可得到 r_i。

只保留最近的冲突位置不会遗漏答案。若 i<j 且 a_i 与 a_j 不互质，则对应质因数集合中，i 的直接后继不晚于 j。任何同时包含 i 和 j 的连续子段，也会包含这个直接后继。因此，以 i 为左端冲突位置时，所有非法子段都能由 i 和 r_i 这一对位置表示。

设长度为 k 的子段起点为 x。它同时包含 i 和 r_i，需要满足 x\le i 与 x+k-1\ge r_i。同时，合法起点范围为 [1,n-k+1]。所以位置 i 对非法起点的贡献区间为：

[\max(1,r_i-k+1),\min(i,n-k+1)]

若左端点大于右端点，该贡献为空。反过来，任意非法子段都包含一对不互质的位置 i<j。由 r_i\le j，该子段也包含 i 和 r_i，其起点一定落在上述区间。于是，所有贡献区间的并集恰好是全部非法子段起点。

用线段树维护这些区间的覆盖次数，以及覆盖次数为正的总长度。根结点保存的覆盖长度就是当前答案。

修改位置 x 时，不需要重新计算所有 r_i。对任意质数，把它整除的位置升序排列。删除或插入 x 只会改变两类直接后继关系：x 自己的后继，以及 x 前一个位置的后继。故可能变化的位置仅包含：

先收集这些位置并去重，再从线段树中删除它们原来的贡献。然后更新质因数位置集合和 a_x，重新计算这些位置的 r_i，最后加入新的贡献。这个顺序保证线段树中的每段覆盖始终对应当前数列。

由于 2\times3\times5\times7\times11\times13\times17>10^5，一个数至多有 6 个不同质因数。筛法预处理的复杂度为 O(V\log\log V)，初始化和每次修改分别为 O(n\log n) 与 O(\log n)。总时间复杂度为 O(V\log\log V+(n+m)\log n)，其中 V=10^5。

参考代码

#include <bits/stdc++.h>
using namespace std;

using ll=long long;
const int N=100005;
int n,k,m,lim;
int a[N],nxt[N],pr[N];
bool use[N];
vector<int> fac[N];
set<int> pos[N];
struct SEG
{
    int val[N*4],tag[N*4];
    void push_up(int u,int l,int r)
    {
        if(tag[u])val[u]=r-l+1;
        else if(l==r)val[u]=0;
        else val[u]=val[u*2]+val[u*2+1];
    }
    void update(int u,int l,int r,int x,int y,int v)
    {
        if(x<=l&&r<=y)tag[u]+=v;
        else
        {
            int mid=l+r>>1;
            if(x<=mid)update(u*2,l,mid,x,y,v);
            if(y>mid)update(u*2+1,mid+1,r,x,y,v);
        }
        push_up(u,l,r);
    }
}T;
int get_nxt(int i)
{
    int res=n+1;
    for(auto p:fac[a[i]])
    {
        auto it=pos[p].upper_bound(i);
        if(it!=pos[p].end())res=min(res,*it);
    }
    return res;
}
void cover(int i,int v)
{
    int l=max(1,nxt[i]-k+1),r=min(i,lim);
    if(l<=r)T.update(1,1,lim,l,r,v);
}
void collect(int x,int v,int s[],int &cnt)
{
    for(auto p:fac[v])
    {
        auto it=pos[p].lower_bound(x);
        if(it!=pos[p].begin())s[cnt++]=*--it;
    }
}
void solve()
{
    lim=n-k+1;
    fill(T.val,T.val+lim*4+5,0);
    fill(T.tag,T.tag+lim*4+5,0);
    int tot=0;
    ll sum=0;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        sum+=a[i];
        for(auto p:fac[a[i]])
        {
            if(!use[p])
            {
                use[p]=1;
                pr[tot++]=p;
            }
            pos[p].insert(i);
        }
    }
    for(int i=1;i<=n;i++)
    {
        nxt[i]=get_nxt(i);
        cover(i,1);
    }
    cout<<T.val[1]<<'\n';
    for(int i=1;i<=m;i++)
    {
        int x,b;
        cin>>x>>b;
        int cnt=1;
        int s[20];
        s[0]=x;
        collect(x,a[x],s,cnt);
        collect(x,b,s,cnt);
        sort(s,s+cnt);
        cnt=unique(s,s+cnt)-s;
        for(int j=0;j<cnt;j++)cover(s[j],-1);
        sum+=b-a[x];
        for(auto p:fac[a[x]])pos[p].erase(x);
        a[x]=b;
        for(auto p:fac[a[x]])
        {
            if(!use[p])
            {
                use[p]=1;
                pr[tot++]=p;
            }
            pos[p].insert(x);
        }
        for(int j=0;j<cnt;j++)
        {
            nxt[s[j]]=get_nxt(s[j]);
            cover(s[j],1);
        }
        cout<<T.val[1]<<'\n';
    }
    cout<<sum<<'\n';
    for(int i=0;i<tot;i++)
    {
        pos[pr[i]].clear();
        use[pr[i]]=0;
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    for(int i=2;i<N;i++)
    {
        if(!fac[i].empty())continue;
        for(int j=i;j<N;j+=i)fac[j].push_back(i);
    }
    while(cin>>n>>k>>m&&n)solve();
    return 0;
}