#include <bits/stdc++.h>
using namespace std;
#define ii pair<int,int>
#define ll long long
int n,q;
int arr[100005];
struct range{
vector<ii> l,r; //maintain running gcd from left and right
//<val, length>
ll init(int i){
l.clear(),r.clear();
l.push_back(ii(i,1));
r.push_back(ii(i,1));
return i!=1;
}
ll merge(range i, range j){ //i hope deep copying happens
ll res=0;
for (auto &it:i.r){
for (auto &it2:j.l){
if (__gcd(it.first,it2.first)!=1) res+=(ll)it.second*it2.second;
}
}
l.clear(),r.clear();
l.insert(l.begin(),i.l.begin(),i.l.end());
for (auto &it:j.l){
if (__gcd(l.back().first,it.first)==l.back().first) l.back().second+=it.second;
else l.push_back(ii(__gcd(l.back().first,it.first),it.second));
}
r.insert(r.begin(),j.r.begin(),j.r.end());
for (auto &it:i.r){
if (__gcd(r.back().first,it.first)==r.back().first) r.back().second+=it.second;
else r.push_back(ii(__gcd(r.back().first,it.first),it.second));
}
return res;
}
} temp; //we use temp for dirty work
ll ans; //this is to get answers
struct node{
int s,e,m;
ll val; //number of good interval here
range dat; //info about this range
node *l, *r;
node (int _s,int _e){
s=_s,e=_e,m=s+e>>1;
if (s!=e){
l=new node(s,m);
r=new node(m+1,e);
val=dat.merge(l->dat,r->dat);
val+=l->val+r->val;
}
else{
val=dat.init(arr[s]);
}
//~ printf("segment: %d %d\n",s,e);
//~ for (auto &it:dat.l) printf("%d-%d ",it.first,it.second);
//~ printf("\n");
//~ for (auto &it:dat.r) printf("%d-%d ",it.first,it.second);
//~ printf("\n\n");
}
void update(int i){
if (s==e) val=dat.init(arr[s]);
else {
if (i<=m) l->update(i);
else r->update(i);
val=dat.merge(l->dat,r->dat);
val+=l->val+r->val;
}
}
void query(int i,int j){
if (s==i && e==j){
ans+=val;
ans+=temp.merge(temp,dat);
}
else{
if (j<=m) l->query(i,j);
else if (m<i) r->query(i,j);
else l->query(i,m),r->query(m+1,j);
}
}
}*root;
int main(){
//freopen("input.txt","r",stdin);
scanf("%d%d",&n,&q);
for (int x=1;x<=n;x++) scanf("%d",&arr[x]);
root=new node(1,n);
int a,b,c;
while (q--){
scanf("%d%d%d",&a,&b,&c);
if (a==1){ //update
arr[b]=c;
root->update(b);
}
else{ //query
ans=0;
temp.init(1);
root->query(b,c);
printf("%lld\n",ans);
}
}
}
Compilation message
garaza.cpp: In constructor 'node::node(int, int)':
garaza.cpp:56:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
56 | s=_s,e=_e,m=s+e>>1;
| ~^~
garaza.cpp: In function 'int main()':
garaza.cpp:103:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
103 | scanf("%d%d",&n,&q);
| ~~~~~^~~~~~~~~~~~~~
garaza.cpp:104:30: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
104 | for (int x=1;x<=n;x++) scanf("%d",&arr[x]);
| ~~~~~^~~~~~~~~~~~~~
garaza.cpp:110:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
110 | scanf("%d%d%d",&a,&b,&c);
| ~~~~~^~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
588 KB |
Output is correct |
| 2 |
Correct |
19 ms |
1384 KB |
Output is correct |
| 3 |
Correct |
35 ms |
2100 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
141 ms |
7680 KB |
Output is correct |
| 2 |
Correct |
230 ms |
11080 KB |
Output is correct |
| 3 |
Correct |
187 ms |
10784 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
429 ms |
18564 KB |
Output is correct |
| 2 |
Correct |
509 ms |
18904 KB |
Output is correct |
| 3 |
Correct |
394 ms |
21460 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
948 ms |
36800 KB |
Output is correct |
| 2 |
Correct |
953 ms |
37340 KB |
Output is correct |
| 3 |
Correct |
684 ms |
35852 KB |
Output is correct |
