#include <bits/stdc++.h>
#define N 100005
using namespace std;
struct Node{
long long val,lp,rp;
vector<pair<int,int>> l,r;
Node(){
val = 0,lp=0,rp=0;
l = r = {{0,0}};
}
Node(long long x,long long a,long b,vector<pair<int,int>>y,vector<pair<int,int>>z){
val = x;
lp = a;
rp = b;
l = y;
r = z;
}
};
Node t[4*N];
Node merge(Node a,Node b){
if(a.val == -1)return b;
if(b.val == -1)return a;
Node ret = a;
ret.val += b.val;
ret.r = b.r;
ret.rp = b.rp;
int cnt = 0;
int n = b.l.size();
while(cnt < n){
if(__gcd(ret.l.back().first,b.l[cnt].first) == ret.l.back().first){
ret.l.back().second = b.l[cnt++].second;
continue;
}
ret.l.push_back({__gcd(ret.l.back().first,b.l[cnt].first),b.l[cnt].second});
cnt++;
}
cnt = 0;
n = a.r.size();
while(cnt < n){
if(__gcd(ret.r.back().first,a.r[cnt].first) == ret.r.back().first){
ret.r.back().second = a.r[cnt++].second;
continue;
}
ret.r.push_back({__gcd(ret.r.back().first,a.r[cnt].first),a.r[cnt].second});
cnt++;
}
cnt = a.r.size()-1;
for(auto u:b.l){
while(cnt >= 0 && __gcd(u.first,a.r[cnt].first) == 1){
cnt--;
}
if(cnt < 0)break;
ret.val += (u.second-b.lp + 1) * (a.rp - a.r[cnt].second + 1);
}
return ret;
}
void upd(int v,int l,int r,int pos,int val){
if(l == r){
t[v] = Node((val != 1),l,r,{{val,l}},{{val,l}});
return;
}
int m = (l+r)/2;
if(pos <= m){
upd(v*2,l,m,pos,val);
}
else upd(v*2+1,m+1,r,pos,val);
t[v] = merge(t[v*2],t[v*2+1]);
}
Node get(int v,int tl,int tr,int l,int r){
if(tr < l || r < tl ){
return Node(-1,-1,-1,{{-1,-1}},{{-1,-1}});
}
if(l <= tl && tr <= r){
return t[v];
}
int tm = (tl+tr)/2;
return merge( get(v*2,tl,tm,l,r), get(v*2+1,tm+1,tr,l,r));
}
void solve(){
int n,q;
cin >> n >> q;
for(int i=1;i<=n;i++){
int a;
cin >> a;
upd(1,1,n,i,a);
//cout << get(1,1,n,1,2).val << endl;
}
while(q--){
int type;
cin >> type;
if(type == 1){
int pos,val;
cin >> pos >> val;
upd(1,1,n,pos,val);
}
if(type == 2){
int l,r;
cin >> l >> r;
cout << get(1,1,n,l,r).val << endl;
}
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
#ifdef Local
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
int t=1;
//cin>>t;
while(t--){
solve();
}
#ifdef Local
cout<<endl<<fixed<<setprecision(2)<<1000.0 * clock() / CLOCKS_PER_SEC<< " milliseconds ";
#endif
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
67 ms |
53612 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
349 ms |
54636 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
942 ms |
56448 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1908 ms |
58996 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
