| 123456 |
- #include <algorithm>
- #include <iostream>
- #include <vector>
- using namespace std;
- struct Node{long long sum=0;int mx=0;};
- int main(){ios::sync_with_stdio(false);cin.tie(nullptr);constexpr int V=1000000;vector<int>d(V+1);for(int x=1;x<=V;++x)for(int y=x;y<=V;y+=x)++d[y];int n,q;cin>>n>>q;vector<int>a(n);for(int&x:a)cin>>x;vector<Node>tr(4*n);auto pull=[&](int u){tr[u]={tr[u*2].sum+tr[u*2+1].sum,max(tr[u*2].mx,tr[u*2+1].mx)};};auto build=[&](auto&&self,int u,int l,int r)->void{if(l==r){tr[u]={a[l],a[l]};return;}int m=(l+r)/2;self(self,u*2,l,m);self(self,u*2+1,m+1,r);pull(u);};auto replace=[&](auto&&self,int u,int l,int r,int ql,int qr)->void{if(qr<l||r<ql||tr[u].mx<=2)return;if(l==r){tr[u].mx=d[tr[u].mx];tr[u].sum=tr[u].mx;return;}int m=(l+r)/2;self(self,u*2,l,m,ql,qr);self(self,u*2+1,m+1,r,ql,qr);pull(u);};auto sum=[&](auto&&self,int u,int l,int r,int ql,int qr)->long long{if(ql<=l&&r<=qr)return tr[u].sum;int m=(l+r)/2;long long s=0;if(ql<=m)s+=self(self,u*2,l,m,ql,qr);if(qr>m)s+=self(self,u*2+1,m+1,r,ql,qr);return s;};build(build,1,0,n-1);while(q--){int type,l,r;cin>>type>>l>>r;--l;--r;if(type==1)replace(replace,1,0,n-1,l,r);else cout<<sum(sum,1,0,n-1,l,r)<<'\n';}}
|
