@[STAR_czy](/user/925716) 你小子很危险啊，luogu差点臭名昭著（逃
by Steve_xh @ 2023-12-31 16:55:05
??罵，还说不玩梗，这不就是要我们写代码给你看？
by 13eric @ 2023-12-31 17:05:08
@[STAR_czy](/user/925716) 经不官方认定，你属于危险人群~~请尽快自首~~
by bca_ @ 2023-12-31 17:10:58
我看你想重温[此帖](https://www.luogu.com.cn/discuss/61884)
by danlao @ 2023-12-31 17:17:19
你现在就只差$\colorbox{orange}{\color{blue}说句闲话}$ 了
by danlao @ 2023-12-31 17:20:13
@[Steve_xh](/user/639198) @[13eric](/user/1008942) @[yaodiguoan](/user/1023793) 请问能不能尝试找出问题呢？
by STAR_czy @ 2023-12-31 17:25:32
哦对，我差点就忘了我来到这个帖子的目的了。
by danlao @ 2023-12-31 17:29:55
我服了你这格式了
by danlao @ 2023-12-31 17:30:38
@[yaodiguoan](/user/1023793) 现在是后面全T了
```cpp
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=1e5+10,maxm=5e7+10,mod=1e9+7;
int n,m,tot,tmpt,a[maxn],root[maxn*5],tmp[maxn],dt[maxm],val[maxm],l[maxm],r[maxm];
ll t[maxn];
queue<int> ljt;
inline int newnode(int x){
int p;
if(ljt.size()) p=ljt.front(),ljt.pop();
else p=++tot;
return l[p]=0,r[p]=0,dt[p]=x,p;
}
int merge(int x,int y){return x&&y?val[x]>val[y]?r[x]=merge(r[x],y),x:(l[y]=merge(x,l[y]),y):x+y;}
void split(int p,int v,int &x,int &y){
if(!(bool)p) return (void)(x=y=0);
if(dt[p]<=v) x=p,split(r[p],v,r[p],y);
else y=p,split(l[p],v,x,l[p]);
}
int build(int lq,int rq){
if(lq>rq) return 0;
if(lq==rq) return newnode(tmp[lq]);
int mid=lq+rq>>1,p=newnode(tmp[mid]);
return l[p]=build(lq,mid-1),r[p]=build(mid+1,rq),p;
}
void get(int x,int k){
if(l[x]) get(l[x],k);
// cout<<x<<","<<dt[x]<<"]";
if(a[dt[x]]%k==0){
a[dt[x]]/=k;
for(int i=dt[x],s=a[dt[x]]*(k-1);i<=n;i+=i&-i) t[i]-=s;
if(a[dt[x]]%k==0) tmp[++tmpt]=dt[x];
}
if(r[x]) get(r[x],k);
ljt.push(x);
}
void midfor(int x){
if(l[x]) midfor(l[x]);
cout<<dt[x]<<" ";
if(r[x]) midfor(r[x]);
}
signed main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;++i){
cin>>a[i];
for(int j=i;j<=n;j+=j&-j) t[j]+=a[i];
for(int j=1;j*j<=a[i];++j) if(a[i]%j==0){
root[j]=merge(root[j],newnode(i));
if(j*j!=a[i]) root[a[i]/j]=merge(root[a[i]/j],newnode(i));
}
}
for(int o=1;o<=m;++o){
int opt,l,r;
cin>>opt>>l>>r;
if(opt==1){
int x,s1,s2,s3;
cin>>x;
split(root[x],r,s2,s3),split(s2,l-1,s1,s2),tmpt=0;
if(s2) get(s2,x),s2=build(1,tmpt);
root[x]=merge(s1,merge(s2,s3));
}
else{
ll ans=0;
for(int i=r;i;i-=i&-i) ans+=t[i];
for(int i=l-1;i;i-=i&-i) ans-=t[i];
cout<<ans<<'\n';
}
}
return 0;
}
by STAR_czy @ 2024-01-05 17:27:13