#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;
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;
vector<int> prefL, prefR;
for (auto u : lft) {
if (prefL.size() == 0)
prefL.push_back(u.s);
else
prefL.push_back(u.s + prefL.back());
}
for (auto u : rght) {
if (prefR.size() == 0)
prefR.push_back(u.s);
else
prefR.push_back(u.s + prefR.back());
}
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 += prefL[i] * prefR[j];
}
}
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.s) < new_node.r_l.back().f)
new_node.r_l.push_back({__gcd(new_node.r_l.back().f, u.s), u.s});
else
new_node.r_l.back().s += u.s;
}
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));
}
int 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:46:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
46 | for (int i = 0; i < lft.size(); i++) {
| ~~^~~~~~~~~~~~
garaza.cpp:47:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
47 | for (int j = 0; j < rght.size(); j++) {
| ~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
17 ms |
24668 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
284 ms |
28892 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
844 ms |
35012 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2027 ms |
45484 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
