#include<bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define ii pair<int,int>
#define all(x) (x).begin(),(x).end()
#define INF 100000000000000000
#define modulo 1000000007
#define mod 998244353
//#define int long long int
using namespace std;
vector<int>arr;
map<int,int>F[100005];
struct node{
long long int cnt;
int size;
map<int,int>pre,suff;
node(int s){
cnt=0;
size=s;
}
void merge(node L,node R){
size=L.size+R.size;
if(L.size==0){
cnt=R.cnt;
pre=R.pre;
suff=R.suff;
return;
}
if(R.size==0){
cnt=L.cnt;
pre=L.pre;
suff=L.suff;
return;
}
pre.clear();
suff.clear();
map<int,int>ind;
ind[0]=0;
for(map<int,int>::iterator itr=L.suff.begin();itr!=L.suff.end();itr++){
ind[itr->second]=max(ind[itr->second],R.pre[itr->first]);
}
int p=ind.rbegin()->first;
int w=ind.rbegin()->second;
for(map<int,int>::reverse_iterator itr=(++ind.rbegin());itr!=ind.rend();itr++){
cnt+=(long long int)((long long int)p-(long long int)itr->first)*(long long int)w;
p=itr->first;
w=max(w,itr->second);
}
cnt+=L.cnt+R.cnt;
pre=L.pre;
for(map<int,int>::iterator itr=L.pre.begin();itr!=L.pre.end();itr++){
if(itr->second==L.size)pre[itr->first]=itr->second+R.pre[itr->first];
}
suff=R.suff;
for(map<int,int>::iterator itr=R.suff.begin();itr!=R.suff.end();itr++){
if(itr->second==R.size)suff[itr->first]=itr->second+L.suff[itr->first];
}
}
};
vector<node>seg;
int S;
void build(){
S=(1<<(int)ceil(log2(seg.size())));
int l=S-seg.size();
for(int i=0;i<l;i++)seg.pb(node(0));
reverse(all(seg));
for(int i=1;i<seg.size();i+=2){
node temp(0);
temp.merge(seg[i],seg[i-1]);
seg.pb(temp);
}
seg.pb(node(0));
reverse(all(seg));
}
node query(int j,int a,int b,int x,int y){
node temp(0);
if(y<a||b<x)return temp;
if(a<=x&&y<=b)return seg[j];
temp.merge(query(j*2,a,b,x,(x+y)/2),query(j*2+1,a,b,(x+y)/2+1,y));
return temp;
}
void update(int j){
while(j>0){
seg[j]=node(0);
seg[j].merge(seg[j*2],seg[j*2+1]);
j/=2;
}
}
int32_t main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
// freopen("q.gir","r",stdin);
// freopen("q.cik","w",stdout);
int n,q;
cin>>n>>q;
seg.resize(n,node(1));
for(int i=0;i<n;i++){
int x;
cin>>x;
arr.pb(x);
for(int j=2;j*j<=x;j++){
if(x%j==0){
F[i][j]=1;
while(x%j==0)x/=j;
}
}
if(x>1)F[i][x]=1;
seg[i].pre=F[i];
seg[i].suff=F[i];
if(F[i].empty())seg[i].cnt=0;
else seg[i].cnt=1;
}
build();
while(q--){
int k,x,y;
cin>>k>>x>>y;
if(k==1){
x--;
F[x].clear();
for(int j=2;j*j<=y;j++){
if(y%j==0){
F[x][j]=1;
while(y%j==0)y/=j;
}
}
if(y>1)F[x][y]=1;
int i=seg.size()-S+x;
seg[i].pre=F[x];
seg[i].suff=F[x];
if(F[x].empty())seg[i].cnt=0;
else seg[i].cnt=1;
update(i/2);
}
else{
x--,y--;
cout<<query(1,x,y,0,S-1).cnt<<"\n";
}
}
}
Compilation message
garaza.cpp: In function 'void build()':
garaza.cpp:67:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=1;i<seg.size();i+=2){
~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
51 ms |
6264 KB |
Output is correct |
| 2 |
Correct |
146 ms |
7600 KB |
Output is correct |
| 3 |
Correct |
214 ms |
12780 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1101 ms |
37308 KB |
Output is correct |
| 2 |
Correct |
715 ms |
32284 KB |
Output is correct |
| 3 |
Correct |
1835 ms |
39808 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1369 ms |
47116 KB |
Output is correct |
| 2 |
Correct |
3598 ms |
78768 KB |
Output is correct |
| 3 |
Correct |
3772 ms |
74604 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2775 ms |
89280 KB |
Output is correct |
| 2 |
Execution timed out |
4024 ms |
164044 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
