Bài F - Eduacational Codeforces Round 37 (Div.2)

Bài F:
Đề bài: Gọi D(x) là số các ước nguyên dương của số x nguyên dương. Ví dụ, D(2)=2 (do 2 chia hết cho 1 và 2), D(6)=4( do 6 chia hết cho 1,2,3 và 6).
  Bạn được cho một mảng a gồm n số nguyên. Bạn phải xử lý hai loại truy vấn sau đây:
1. REPLACE l r - với mọi i thuộc [l;r] nghĩa là thay a(i) bởi D(a(i)).
2. SUM l r - nghĩa là tính tổng $\sum\limits_{i=l}^{r}a_i$.
In ra câu trả lời cho mỗi truy vấn SUM.
Đầu vào:
+ Dòng đầu tiên chứa hai số nguyên n và m (1<=n,m<=3.10^5) - số phần tử trong mảng và số truy vấn cần xử lý, lần lượt.
+ Dòng thứ hai chứa n số nguyên a(1),a(2),...,a(n) (1<=a(i)<=10^6) - các phần tử trong mảng.
+ m dòng tiếp theo, mỗi dòng chứa 3 số nguyên t(i),l(i) và r(i) kí hiệu truy vấn thứ i. Nếu t(i)=1, thì truy vấn thứ i là REPLACE l(i) r(i), mặt khác, nó là SUM l(i) r(i) (1<=t(i)<=2,1<=l(i)<=r(i)<=n).
Có ít nhất 1 truy vấn SUM.
Đầu ra:
Với mỗi truy vấn SUM, in ra câu trả lời cho nó.
Ví dụ:
7 6
6 4 1 10 3 2 4
2 1 7
2 4 5
1 3 5
2 4 4
1 5 7
2 1 7
Đầu ra:
30
13
4
22.
Hướng dẫn:
Lời giải:

#include<cstdio>
const int N=1000006;
int n,m,i,j,k,a[N],d[N],f[N],opt,l,r;
long long c[N],s;
int p(int x){
 return x==f[x]?x:f[x]=p(f[x]);
}
void add(int x,int y){
 while(y<=n)
  c[y]+=x,y+=y&-y;
}
long long sum(int x){
 for(s=0;x;x-=x&-x)
  s+=c[x];
 return s;
}
int main(){
 for(i=1;i<N;i++)
  for(j=i;j<N;j+=i)
   d[j]++;
 scanf("%d%d",&n,&m);
 for(i=1;i<=n;i++){
  scanf("%d",a+i);
  add(a[i],i);
  if(a[i]>2)
   f[i]=i;
  else
   f[i]=i+1;
 }
 f[i]=i;
 while(m--){
  scanf("%d%d%d",&opt,&l,&r);
  if(opt==1){
   while((l=p(l))<=r){
    add(-a[l],l);
    a[l]=d[a[l]];
    add(a[l],l);
    if(a[l]<=2)
     f[l]=l+1;
    l++;
   }
  }
  else
   printf("%lld\n",sum(r)-sum(l-1));
 }
}