题解

题目分析

这是一道算法题目，需要根据具体题目要求进行求解。

解题思路

1. 问题分析

• 仔细阅读题目描述，理解题目要求
• 分析输入输出格式和约束条件
• 确定需要使用的算法和数据结构

2. 算法选择

• 根据题目特点选择合适的算法
• 考虑时间复杂度和空间复杂度
• 确保算法能正确处理所有测试用例

3. 实现要点

• 注意边界条件的处理
• 优化输入输出以提高效率
• 确保代码的正确性和鲁棒性

4. 调试和优化

• 使用测试用例验证算法正确性
• 分析性能瓶颈并进行优化
• 确保代码能通过所有测试点

注意事项

• 仔细处理数据类型和精度问题
• 注意数组越界和空指针问题
• 确保算法的时间复杂度符合要求

#include<bits/stdc++.h>
#define reg register
// #define int long long
inline int read(){
    reg int x=0,k=1; reg char ch=getchar();    
    while (ch<'0'||ch>'9') (ch=='-')&&(k=-1),ch=getchar();
    while ('0'<=ch&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x*k;
}
const int N=1e6+10;
int n,m,q,pos[N],cnt[N][21],a[N];
int f[N],val[N],Cnt[30];
std::vector<int> vc[N];
int L,R;
inline int get(reg int x){
    for (reg int i=20;i;i--) if (cnt[x][i]) return i+1;
    return 1;
}
inline void upd(reg int x,reg int F,reg int v){
    for (auto it:vc[x]) if (pos[it]&&pos[it]<pos[x]) 
        cnt[it][F]+=v;
}
inline void getans(){for (reg int i=20;i;i--) if (Cnt[i]) return printf("%d %d\n",i,Cnt[i]),void();}
inline void insl(reg int x){
    memset(cnt[x],0,sizeof(cnt[x]));
    for (reg int i=x+x;i<=m;i+=x) if (pos[i]) 
        cnt[x][f[i]]++;
    Cnt[f[x]=get(x)]++,val[--L]=x,pos[x]=L; 
}
inline void dell(){Cnt[f[val[L]]]--,pos[val[L]]=0,L++;}
inline void insr(reg int x){
    Cnt[f[x]=1]++,val[++R]=x,pos[x]=R,upd(x,1,1);
    memset(cnt[x],0,sizeof(cnt[x]));
    for (auto it:vc[x])if (pos[it]){
        reg int his=f[it]; f[it]=get(it);
        if (f[it]!=his){
            Cnt[his]--,Cnt[f[it]]++;
            upd(it,his,-1),upd(it,f[it],1);
        }
    }
}
inline void delr(){
    Cnt[f[val[R]]]--,upd(val[R],f[val[R]],-1);
    // std::cerr<<"<< "<<val[R]<<" "<<f[val[R]]<<"\n";
    for (auto it:vc[val[R]])if (pos[it]){
        reg int his=f[it]; f[it]=get(it);
        if (f[it]!=his){
            Cnt[his]--,Cnt[f[it]]++;
            upd(it,his,-1),upd(it,f[it],1);
        }
    }
    pos[val[R]]=0,R--;
}
signed main(){ 
    n=read(),m=read(),q=read();
    for (reg int i=1;i<=n;i++) a[i]=read();
    for (reg int i=m;i;i--) for (reg int j=i+i;j<=m;j+=i) 
        vc[j].push_back(i);
    R=100003+n,L=R+1;
    for (reg int i=n;i;i--) insl(a[i]);
    // std::cerr<<"<< "<<f[1]<<" "<<f[2]<<" "<<f[3]<<" "<<Cnt[6]<<"\n";
    getans();
    while (q--){
        reg int op=read();
        if (op==0) insl(read());
        else if (op==1) insr(read());
        else if (op==2) dell();
        else delr();
        getans();
    }
    return 0;
}