#include <bits/stdc++.h>
using namespace std;
#define fast ios::sync_with_stdio(0);cin.tie(0);
#define s second
#define f first
typedef long long ll;
const ll MOD = 1e9 + 7;
const ll LOGN = 21;
const ll MAXN = 1e5 + 10000;
#define int long long
struct Node {
ll ans;
vector<pair<int,int>> l_r, r_l;
Node() { ans = 0; }
};
Node sg[4*MAXN];
vector<int> A;
Node merge(Node A, Node B) {
Node new_node;
new_node.ans = A.ans + B.ans;
new_node.l_r.push_back({0, 0});
new_node.r_l.push_back({0, 0});
for (auto u : A.l_r)
new_node.l_r.push_back(u);
for (auto u : B.r_l)
new_node.r_l.push_back(u);
vector<pair<int,int>> lft = A.r_l;
vector<pair<int,int>> rght = B.l_r;
for (int i = 0; i < lft.size(); i++) {
for (int j = 0; j < rght.size(); j++) {
if (__gcd(lft[i].f, rght[j].f) != 1)
new_node.ans += lft[i].s * rght[j].s;
}
}
for (auto u : B.l_r) {
if (__gcd(new_node.l_r.back().f, u.f) < new_node.l_r.back().f)
new_node.l_r.push_back({__gcd(new_node.l_r.back().f, u.f), u.s});
else
new_node.l_r.back().s += u.s;
}
for (auto u : A.r_l) {
if (__gcd(new_node.r_l.back().f, u.f) < new_node.r_l.back().f)
new_node.r_l.push_back({__gcd(new_node.r_l.back().f, u.f), u.s});
else
new_node.r_l.back().s += u.s;
}
reverse(new_node.l_r.begin(), new_node.l_r.end());
new_node.l_r.pop_back();
reverse(new_node.l_r.begin(), new_node.l_r.end());
reverse(new_node.r_l.begin(), new_node.r_l.end());
new_node.r_l.pop_back();
reverse(new_node.r_l.begin(), new_node.r_l.end());
return new_node;
}
void init(int k, int a, int b) {
if (a == b) {
sg[k].ans = (A[a] > 1);
sg[k].l_r.push_back({A[a], 1});
sg[k].r_l.push_back({A[a], 1});
return ;
}
init(2*k, a, (a+b)/2);
init(2*k+1, (a+b)/2+1, b);
sg[k] = merge(sg[2*k], sg[2*k+1]);
}
void update(int k, int a, int b, int plc, int val) {
if (b < plc || a > plc)
return ;
if (a == b) {
A[a] = val;
sg[k].ans = (A[a] > 1);
sg[k].l_r.clear();
sg[k].r_l.clear();
sg[k].l_r.push_back({A[a], 1});
sg[k].r_l.push_back({A[a], 1});
return ;
}
update(2*k, a, (a+b)/2, plc, val);
update(2*k+1, (a+b)/2+1, b, plc, val);
sg[k] = merge(sg[2*k], sg[2*k+1]);
}
Node query(int k, int a, int b, int q_l, int q_r) {
if (b < q_l || a > q_r)
return Node();
if (q_l <= a && b <= q_r)
return sg[k];
return merge(query(2*k, a, (a+b)/2, q_l, q_r),
query(2*k+1, (a+b)/2+1, b, q_l, q_r));
}
void main() {
fast
int N, Q;
cin >> N >> Q;
A = vector<int>(N+1);
for (int i = 1; i <= N; i++)
cin >> A[i];
init(1, 1, N);
while (Q--) {
int type, a, b;
cin >> type >> a >> b;
if (type == 1)
update(1, 1, N, a, b);
else
cout << query(1, 1, N, a, b).ans << "\n";
}
}
Compilation message
garaza.cpp: In function 'Node merge(Node, Node)':
garaza.cpp:33:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
33 | for (int i = 0; i < lft.size(); i++) {
| ~~^~~~~~~~~~~~
garaza.cpp:34:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
34 | for (int j = 0; j < rght.size(); j++) {
| ~~^~~~~~~~~~~~~
garaza.cpp: At global scope:
garaza.cpp:100:1: error: '::main' must return 'int'
100 | void main() {
| ^~~~
