Need help with this question. Can someone suggest me how to code this problem i need a full editorial for the question
please see this…
#include <bits/stdc++.h>
using namespace std;
bool sieve[1000001];
long long int pf[1000001]={0};
long long bit[1000002];
struct event{
int l,r,k,ind;
}que[100002];
void prime(){
for(int i=0;i<1000001;i++)
sieve[i]=true;
sieve[0]=sieve[1]=false;
for(int i=2;ii<1000001;i++){
if(sieve[i]==true){
pf[i]+=i;
for(int j=i2;j<1000001;j+=i){
sieve[j]=false;
pf[j]+=i;
}
}
}
}
bool compare(struct event a, struct event b){
return a.k<b.k;
}
void update(int index,long long int val){
for(;index<=1000000;index+=index&(-index))
bit[index]+=val;
}
long long int query(int index){
long long int ans=0;
for(;index>0;index-=index&(-index)){
ans+=bit[index];
}
return ans;
}
int main()
{
std::ios_base::sync_with_stdio(false);
prime();
long long int n,q;
cin>>n>>q;
// map<int,int> m;
//map<int,int>:: iterator it;
vector v;
long long int e;
for(int i=1;i<=n;i++){
cin>>e;
v.push_back(e);
update(i,i*pf[e]);
}
for(int i=0;i<q;i++){
cin>>que[i].l>>que[i].r>>que[i].k;
que[i].ind=i;
}
sort(que,que+q,compare);
long long int ans[q+1];
for(int i=0;i<q;i++){
it=m.begin();
while(it->first <= que[i].k){
update(it->second,-(it->first)*(it->second));
m.erase(it);
it=m.begin();
}
ans[que[i].ind]=query(que[i].r)-query(que[i].l - 1);
}
for(int i=0;i<q;i++)
cout<<ans[i]<<endl;
return 0;
}
here I have tried to code it but its giving tle.