算是大学那题的弱化版？时限放到了 4s，也不强制在线了qwq

其实是大学那题把我卡没了/kk

Description

给一个长为 $n$ 的序列 $A$，有 $m$ 次操作，需要支持：

• 给区间 $[l,r]$ 内所有 $x$ 的倍数除以 $x$
• 区间求和

$1\le n,m\le10^5,0\le A_i\le5\times10^5,1\le x\le5\times10^5$。

Solution

区间求和就不多说了吧qwq。

这里主要说一下第一种操作。

看到操作后立马感觉懒标记之类的基本不可能......

所以咋办/fad

我们考虑一个数不管除以个什么东西，都会至少减半。

所以对于 $A_i$，顶多给它除个 $\log A_i$ 次就会变成 $1$，然后就不是任何数的倍数，除以 $1$ 也不会再变，不用再去管他了。

所以用一种类似 GSS4 那道的思想，我们直接找到每个需要修改的数，一个一个修改。

ps：那题我也写了题解，欢迎参观qwq

然后这题的难点就在于：怎么快速找到应该修改的数啊orz。

这不像 GSS4，那个给定了是一个区间内的所有数，但是这题修改的可不是整个区间啊qwq......

如果暴力扫一遍修改区间显然不可能。

之前看到这题之后就直接卡到了这里，然后弃疗了qwq。

直到某谷网校第三次tg模拟赛的时候出了某个题，大概也是约数相关的，于是学到了用冰茶姬来处理约数个数的好办法qwq（

（题目保密，想看题目请左转报名秋令营）

所以我们回来说说这道题该怎么处理。

由于 $A_i$ 和 $x$ 的范围只有 $5\times10^5$，所以我们直接用 DS，对于每一个 $k$，处理出序列 $A$ 中所有 $k$ 的倍数的位置。

这个很好处理，直接输入的时候随便搞一下就行了。

那么我们看看要对这个数据结构进行什么操作：

• 由于除以 $k$ 可能会导致这个数不再是 $k$ 的倍数，所以需要支持删除操作。
• 由于限定了要在 $[l,r]$ 中找数，所以还需要支持 lower_bound。
• 然后显然要支持单点查询。

此时答案已经呼之欲出了：直接 Splay 或者 Treap 之类的平衡树硬搞就行了！

那么我们对于 $1\le k\le 5\times10^5$ 的所有 $k$，建一棵平衡树维护就行了。

也就是说，建 $5\times 10^5$ 棵平衡树。

然而我说过，我用的是冰茶姬，那么冰茶姬该怎么搞呢qwq

我们在我们维护的这个序列（注意，是我们维护的这个序列，也就是 $k$ 的所有倍数这个，而不是原序列 $A$）中，对每个位置，预处理出它的下一个没有被删除的位置 it。

显然初始每个 it 都指向自己。

然后 lower_bound 的时候直接用这些 it 来处理就行了，这些 it 可以直接用冰茶姬维护。

所以说和某谷网校的那个模拟题没啥联系，冰茶姬的处理方式都不一样

这样的话就没什么问题了qwq。

最后提一嘴复杂度：预处理复杂度是 $O(n\sqrt{A})$，单次操作显然是 $O(\log n)$，所以总复杂度为：$O(n\sqrt{A}+m\log n)$。

#include<cstdio>
#include<algorithm>
#include<vector>
#include<cstdlib>
#include<cstring>
#include<cctype>
#include<iostream>

#define MAXN 100005
#define LL long long
#define RE register
#define int long long

using namespace std;

inline LL qread(){
    RE char ch=getchar();
    RE LL x=0,f=1;
    while(ch<'0'||ch>'9'){
        if(ch=='-')f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<3)+(x<<1)+ch-48;
        ch=getchar();
    }
    return x*f;
}

int a[MAXN];
int n,m;
LL c[MAXN];
vector<int>it[500005];

vector<int>fa[500005];
inline int find(int x,int v){
    if(v==fa[x].size()||v==fa[x][v])return (v);
    return (fa[x][v]=find(x,fa[x][v]));
}

struct BIT{
    inline int lowbit(int x){
        return x&(-x);
    }

    inline void modify(int x,LL k){
        for(RE int i=x;i<=n;i+=lowbit(i)){
            c[i]+=k;
        }
    }

    inline LL Sum(int x){
        LL ans=0;
        for(RE int i=x;i;i-=lowbit(i)){
            ans+=c[i];
        }
        return ans;
    }
};
BIT tree;

inline void pre(){
    n=qread();
    m=qread();
    for(RE int i=1;i<=n;i++){
        a[i]=qread();
        tree.modify(i,a[i]);
    }
    for(RE int i=1;i<=n;i++){
        for(RE int j=1;j*j<=a[i];j++){
            if(a[i]%j==0){
                it[j].push_back(i);
                fa[j].push_back(fa[j].size());
                if(j*j!=a[i]){
                    it[a[i]/j].push_back(i);
                    fa[a[i]/j].push_back(fa[a[i]/j].size());
                }
            }
        }
    }
}

inline void change(int l,int r,int x){
    int pos=find(x,lower_bound(it[x].begin(),it[x].end(),l)-it[x].begin());
    while(pos<it[x].size()&&it[x][pos]<=r){
        int u=it[x][pos];
        if(a[u]%x==0){
            tree.modify(u,a[u]/x-a[u]);
            a[u]/=x;
        }
        if(a[u]%x!=0)fa[x][pos]=pos+1;
        pos=find(x,pos+1);
    }
}

signed main(void){

    pre();
    LL ans=0;
    while(m--){
        int op,l,r;
        op=qread();
        l=qread();
        r=qread();
        if(l>=r)swap(l,r);
        if(op==1){
            LL x=qread();
            if(x==1)continue;
            change(l,r,x);
        }
        else{
            ans=tree.Sum(r)-tree.Sum(l-1);
            printf("%lld\n",ans);
        }
    }

    return 0;
}