AYWK Editorial

[agarwal_keshav]

PROBLEM LINK:

Are You Worthy

Author: agarwal_keshav
Tester: dragno99
Editorialist: agarwal_keshav

DIFFICULTY:

MEDIUM-HARD

PROBLEM:

Given an array a consisting of n numbers and we can ask you 2 type of query-

• Type 1- Given an integer i and v (0 \leq i \leq n−1) Change the value of the a_i with v.

• Type 2 - you are given two integer l and r such that (0≤l≤r≤n−1) Print the number of distinct prime factors in (a_l + a_{l+1} + ... + a_r) which are not the factors of any a_t where l≤t≤r.

Prerequisites:

• segment tree

EXPLANATION:

well we can use segment tree to update the elements in array as well as to find the sum in range from l to r. we can also use the sieve and shortest prime factor method to find the prime factors of any number but now the question is how we will check that a particular prime factor of sum is also a factor of any array element indexed from l to r or not. to solve this we can do one thing, corresponding to prime factor x we will store all the array index i such that x is a factor of a_i and then to check should we count the prime factor let’s say x of sum in range l to r for our answer or not we will apply binary search over set[x] and check if any element in the range l to r present in our set or not.

SOLUTIONS:

Setter's Solution

#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define nl cout<<"\n";
#define fix(f,n) cout<<fixed<<setprecision(n)<<f
const int mod = 1e9+7;
template<typename ...T>
void debug(T&&... args){ ((cerr << args << " "), ...);cerr<<"\n";}
ll gcd(ll a,ll b){ return a?gcd(b%a,a):b; }
ll minv(ll a,ll b){ return a<b?a:b;}
ll maxv(ll a,ll b){ return a>b?a:b;}
void swapv(ll &a,ll &b){a=a+b;b=a-b;a=a-b;}
ll power(ll a, ll b, ll m=mod){
   if(a==0 || b==1) return a;
   if(b==0) return 1;ll ans=1;
   while(b>=1){ if(b&1){b--;ans = (ans*a) % m;}a = (a*a)% m;b = b>>1;}return ans;
}
ll logv(ll x){ll ans =-1;while(x){x = x>>1;ans++;}return ans;}
ll inv(ll a,ll m){return power(a,m-2,m);}
const ll mxSize = 1e6 + 5;
ll spf[mxSize];
ll primes[60];

void sieve(){
   for(int i=1;i<mxSize;i++) spf[i] = i;
   int k=0;
   for(int i=2;i*i<mxSize;i++){
       if(spf[i]==i){
           if(k<60){
               primes[k] = i;
               k++;
           }
           for(int j=i*i;j<mxSize;j+=i){
               if(spf[j]==j) spf[j] = i;
           }
       }
   }
}


ll findNumOfPrime(ll num,unordered_map<ll,set<ll>> &mp,ll l,ll r){
   ll count = 0;
   while(num > 1){
       ll fact = spf[num];
       auto it = mp[fact].lower_bound(l);
       if((it==mp[fact].end()) || (*it > r)){
           count++;
       }
       while(spf[num]==fact){
           num = num/fact;
       }
   }
   return count;
}

class segTree{
   public:
   vector<ll> vec;
   ll size;
   segTree(int n){
       size = n;
       vec.resize(4*n);
   }
   void insert(int l,int r,int index,ll val1,ll i){
       if((l>i) || (r<i)) return;
       if(l==r){
           vec[index] = val1;
           return;
       }
       int mid = l + (r - l)/2;
       int child1 = 2*index + 1;
       int child2 = 2*index + 2;
       insert(l,mid,child1,val1,i);
       insert(mid+1,r,child2,val1,i);
       vec[index] = vec[child1] + vec[child2];
   }

   void insert(ll val,ll i){
       insert(0,size-1,0,val,i);
   }
   
   ll query(ll lrange, ll rrange,ll left,ll right,ll index){
       if((rrange < left) || (lrange > right)){
           return 0;
       }
       if((lrange >= left) && (rrange <= right)){
           return vec[index];
       }
       ll mid = lrange + (rrange - lrange)/2;
       return query(lrange,mid,left,right,2*index+1) + query(mid + 1,rrange,left,right,2*index+ 2);
   }

   ll query(ll l,ll r){
       return query(0,size-1,l,r,0);
   }
};

void addPrime(unordered_map<ll,set<ll>> &mp,ll num,ll index){
   while(num > 1){
       ll fact = spf[num];
       mp[fact].insert(index);
       while(spf[num]==fact){
           num = num/fact;
       }
   }
}

void removePrime(unordered_map<ll,set<ll>> &mp,ll num,ll index){
   while(num > 1){
       ll fact = spf[num];
       mp[fact].erase(index);
       while(spf[num]==fact){
           num = num/fact;
       }
   }
}


int main() {
   ios_base::sync_with_stdio(false); 
   cin.tie(NULL);  
   #ifndef ONLINE_JUDGE 
       freopen("input.txt", "r", stdin); 
       freopen("output.txt", "w", stdout);
       freopen("error.txt","w",stderr); 
   #endif 
   sieve();
   ll n,q;
   cin>>n>>q;
   ll a[n];
   segTree tree(n);
   unordered_map<ll,set<ll>> mp;
   for(int i=0;i<n;i++){
       ll x;cin>>x;
       a[i] = x;
       addPrime(mp,a[i],i);
       tree.insert(x,i);
   }
   while(q--){
       int type;
       cin>>type;
       if(type==1){
           ll i,v;
           cin>>i>>v;
           removePrime(mp,a[i],i);
           a[i] = v;
           addPrime(mp,a[i],i);
           tree.insert(v,i);
       }else{
           ll l,r;
           cin>>l>>r;
           ll sum;
           sum = tree.query(l,r);
           cout<<findNumOfPrime(sum,mp,l,r);nl;
       }
   }
   return 0;
}

Tester's Solution

#include "bits/stdc++.h"

using namespace std;


template<typename T>
class SegTree{
private:
   void update(int id,const int pos,const T val,int s,int e){
       if(s>e) return;
       if(s==e){ // base case
           v[id] = val;
           return;
       }
       int mid = (s+e)/2;
       if(pos<=mid) update(2*id,pos,val,s,mid);
       else update(2*id+1,pos,val,mid+1,e);
       v[id] = join(v[2*id],v[2*id+1]);
       return;
   }
   T query(int id,const int l,const int r,const int s,const int e){
       if(s>e || r<s || l>e) return dummy;
       else if(l<=s && e<=r) return v[id];
       else return join(query(2*id,l,r,s,(s+e)/2),query(2*id+1,l,r,(s+e)/2+1,e));
   }
public:
   int n;
   vector<T> v; 
   T dummy; // dummy node
   function<T(const T&,const T&)> join;
   SegTree(int n,T dummy,function<T(const T&,const T&)> join):n(n), join(join), dummy(dummy), v(4*n,dummy){}
   void update(const int pos,const T val){ update(1,pos,val,1,n); }
   T query(const int l,const int r){ return query(1,l,r,1,n); }
};

const int N = 1e6 + 10;
int spf[N];

unordered_map<int,set<int>> m;

void gen(){
   for(int i=0;i<N;i++) spf[i] = i;
   for(int i=2;i<N;i++){
       if(spf[i] == i){
           for(int j=i;j<N;j+=i){
               if(spf[j] == j){
                   spf[j] = i;
               }
           }
       }
   }
}

vector<int> getPfac(int x){
   vector<int> ans;
   while(x > 1){
       int f = spf[x];
       ans.push_back(f);
       while(x % f == 0){
           x/=f;
       }
   }
   return ans;
}

void addInMap(int x,int id){
   auto curr = getPfac(x);
   for(auto &p: curr){
       m[p].insert(id);
   }
}

void removeFromMap(int x,int id){
   auto curr = getPfac(x);
   for(auto &p: curr){
       m[p].erase(id);
       if(m[p].size() == 0){
           m.erase(p);
       }
   }
}

int getAns(int sum , int l,int r){
   int ans = 0;
   auto primeFac = getPfac(sum);
   for(auto &i: primeFac){
       if(m.count(i)){
           auto it = m[i].lower_bound(l);
           if(it == m[i].end() || *it > r){
               ans++;
           }
       }
       else ans++;
   }
   return ans;
}




void __sol(){

   int n,q; cin >> n >> q;

   SegTree<long long> s(n , 0LL , [&](long long x,long long y){
       return x + y;
   });
   
   vector<int> v(n);

   for(int i=0;i<n;i++){
       cin >> v[i];
       addInMap(v[i] , i);
       s.update(i+1 , v[i]);
   }

   while(q--){
       int type; cin >> type;
       if(type == 1){
           int i,x; cin >> i >> x;
           removeFromMap(v[i] , i);
           v[i] = x;
           addInMap(v[i] , i);
           s.update(i + 1, x);
       }
       else{
           int l,r; cin >> l >> r;
           cout << getAns( s.query(l + 1 , r + 1)  , l , r) << "\n";
       }
   }


   return;
}


int main(){
   gen();
   int tc=1;  // cin >> tc;
   while(tc--) __sol();
   return 0;
}