#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];
inline bool comp(ii& a,ii& b){
return a.first>b.first||(a.first==b.first&&a.second>b.second);
}
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();
vector<ii>ind;
ind.pb({0,0});
for(map<int,int>::iterator itr=L.suff.begin();itr!=L.suff.end();itr++){
ind.pb({itr->second,R.pre[itr->first]});
}
sort(all(ind),comp);
int w=ind[0].second;
for(int i=1;i<ind.size();i++){
cnt+=(long long int)((long long int)ind[i-1].first-(long long int)ind[i].first)*(long long int)w;
w=max(w,ind[i].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;
inline 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));
}
vector<node>t;
inline void query(int j,int a,int b,int x,int y){
t[j]=node(0);
if(y<a||b<x)return;
if(a<=x&&y<=b)t[j]=seg[j];
else{
query(j*2,a,b,x,(x+y)/2),query(j*2+1,a,b,(x+y)/2+1,y);
t[j].merge(t[j*2],t[j*2+1]);
t[j*2]=node(0),t[j*2+1]=node(0);
}
}
inline 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;
scanf("%d %d",&n,&q);
seg.resize(n,node(1));
for(int i=0;i<n;i++){
int x;
scanf("%d",&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();
t.resize(seg.size(),node(0));
while(q--){
int k,x,y;
scanf("%d %d %d",&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--;
query(1,x,y,0,S-1);
printf("%d\n",t[1].cnt);
}
}
}
Compilation message
garaza.cpp: In member function 'void node::merge(node&, node&)':
garaza.cpp:47:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=1;i<ind.size();i++){
~^~~~~~~~~~~
garaza.cpp: In function 'void build()':
garaza.cpp:69:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=1;i<seg.size();i+=2){
~^~~~~~~~~~~
garaza.cpp: In function 'int32_t main()':
garaza.cpp:144:41: warning: format '%d' expects argument of type 'int', but argument 2 has type 'long long int' [-Wformat=]
printf("%d\n",t[1].cnt);
^
garaza.cpp:101:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d",&n,&q);
~~~~~^~~~~~~~~~~~~~~
garaza.cpp:105:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&x);
~~~~~^~~~~~~~~
garaza.cpp:123:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d",&k,&x,&y);
~~~~~^~~~~~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
49 ms |
6556 KB |
Output is correct |
| 2 |
Correct |
54 ms |
8856 KB |
Output is correct |
| 3 |
Correct |
192 ms |
15368 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
863 ms |
48632 KB |
Output is correct |
| 2 |
Correct |
732 ms |
37064 KB |
Output is correct |
| 3 |
Correct |
1782 ms |
51840 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1255 ms |
63260 KB |
Output is correct |
| 2 |
Correct |
3210 ms |
99284 KB |
Output is correct |
| 3 |
Correct |
3841 ms |
97964 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2778 ms |
120848 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
