#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
//#include <ext/pb_ds/tree_policy.hpp>
//#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
//using namespace __gnu_pbds;
#define FOR(i,start,end) for(int i=start;i<(int)(end);i++)
#define FORE(i,start,end) for(int i=start;i<=(int)end;i++)
#define RFOR(i,start,end) for(int i = start; i>end; i--)
#define RFORE(i,start,end) for(int i = start; i>=end; i--)
#define vsort(a) sort(a.begin(), a.end());
#define mp make_pair
#define v vector
#define sf scanf
#define pf printf
typedef long long ll;
typedef pair<int, int > pii;
//template <class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
void io();
int __gcd(int x, int y) {
if (x < y)
return __gcd(y, x);
if (y == 0)
return x;
else
return __gcd(y, x%y);
}
struct Node {
ll cnt;
v<pii> pref, suff; // gcd val, number
Node() {
cnt = -1;
}
Node(int a) {
if (a == 1) cnt = 1;
else cnt = 0;
pref.push_back({ a,1 });
suff.push_back({ a,1 });
}
Node(Node &a, Node &b) {
assert(!a.pref.empty() && !b.pref.empty());
// make pref
for (pii x : a.pref)
pref.push_back(x);
for (pii x : b.pref) {
pii add = { __gcd(a.pref.back().first, x.first), x.second };
if (pref.back().first == add.first)
pref.back().second += add.second;
else
pref.push_back(add);
}
// make suff
RFORE(i, b.suff.size() - 1, 0)
suff.push_back(b.suff[i]);
RFORE(i, a.suff.size() - 1, 0) {
pii add = { __gcd(a.suff[i].first, b.suff[0].first), a.suff[i].second };
if (suff.back().first == add.first)
suff.back().second += add.second;
else
suff.push_back(add);
}
reverse(suff.begin(), suff.end());
cnt = a.cnt + b.cnt;
v<ll> bprefsums(b.pref.size());
bprefsums[b.pref.size() - 1] = b.pref.back().second;
RFORE(i, b.pref.size() - 2, 0) bprefsums[i] = bprefsums[i + 1] + b.pref[i].second;
for (int i = 0, j = 0; i < a.suff.size(); i++) {
while (j + 1 < b.pref.size() && __gcd(a.suff[i].first, b.pref[j].first) > 1)
j++;
if (__gcd(a.suff[i].first, b.pref[j].first) > 1)
break;
cnt += (ll)a.suff[i].second*bprefsums[j]; // sum b.pref[j].second->end
}
}
bool isId() {
if (cnt == -1) return 1;
return 0;
}
};
template<int SZ, class T> struct SegmentTree {
T data[2 * SZ];
int _N;
T id = Node(); // identity function (a,id) = a; (id,a) = a;
T combine(T a, T b) {
if (a.isId()) return b;
if (b.isId()) return a;
return Node(a, b);
}
SegmentTree() {}
void build(int N) {
_N = N;
// ! make sure you do this first
// for (int i = 0; i < n; ++i) scanf("%d", t + n + i);
for (int i = _N - 1; i > 0; --i)
data[i] = combine(data[i << 1], data[(i << 1) | 1]);
}
void update(int p, T val) {
data[p += _N] = val;
for (p >>= 1; p > 0; p >>= 1)
data[p] = combine(data[p << 1], data[(p << 1) | 1]);
}
T query(int l, int r) { // sum [l,r]
r++;
T resl = id, resr = id;
for (l += _N, r += _N; l < r; l >>= 1, r >>= 1) {
if (l & 1) resl = combine(resl, data[l++]);
if (r & 1) resr = combine(data[--r], resr);
}
return combine(resl, resr);
}
};
SegmentTree<100010, Node> stree;
int main() {
io();
int N, Q;
cin >> N >> Q;
FOR(i, 0, N) {
int a;
cin >> a;
stree.data[i + N] = Node(a);
}
stree.build(N);
FOR(i, 0, Q) {
int t, a, b;
cin >> t >> a >> b;
if (t == 1)
stree.update(a - 1, Node(b));
else {
ll len = b - a + 1;
len = len*(len - 1) / 2 + len;
cout << len - stree.query(a - 1, b - 1).cnt << "\n";
}
}
return 0;
}
void io() {
#ifdef LOCAL_PROJECT
freopen("input.in", "r", stdin);
freopen("output.out", "w", stdout);
#else
// add i/o method of specific testing system
#endif
ios_base::sync_with_stdio(false);
cin.tie(NULL);
}
Compilation message
garaza.cpp: In constructor 'Node::Node(Node&, Node&)':
garaza.cpp:78:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0, j = 0; i < a.suff.size(); i++) {
~~^~~~~~~~~~~~~~~
garaza.cpp:79:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while (j + 1 < b.pref.size() && __gcd(a.suff[i].first, b.pref[j].first) > 1)
~~~~~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
24 ms |
11512 KB |
Output is correct |
| 2 |
Correct |
39 ms |
11896 KB |
Output is correct |
| 3 |
Correct |
64 ms |
12212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
297 ms |
14392 KB |
Output is correct |
| 2 |
Correct |
384 ms |
16628 KB |
Output is correct |
| 3 |
Correct |
454 ms |
16944 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
805 ms |
20492 KB |
Output is correct |
| 2 |
Correct |
1118 ms |
22380 KB |
Output is correct |
| 3 |
Correct |
1018 ms |
24740 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1543 ms |
32540 KB |
Output is correct |
| 2 |
Correct |
1966 ms |
35112 KB |
Output is correct |
| 3 |
Correct |
2015 ms |
36308 KB |
Output is correct |
