#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
struct qhash
{
static uint64_t splitmix64(uint64_t x)
{
// http://x...content-available-to-author-only...i.it/splitmix64.c
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
size_t operator()(uint64_t x)
const
{
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(x + FIXED_RANDOM);
}
};
typedef long long ll;
typedef bool bl;
typedef string str;
typedef unsigned long long ull;
typedef double db;
#define fi first
#define se second
#define mp(p1, p2) make_pair(p1, p2)
#define f(i, n) for (ll i = 0; i < n; i += 1)
#define fv(i, v) for (typeof(v.begin()) i = v.begin(); i != v.end(); i++)
#define fu(i, start, end) for (int i = start; i < end; i += 1)
#define fd(i, start, end) for (int i = start; i >= end; i -= 1)
#define BIT(var, pos) ((bool)((var) & (1 << (pos))))
#define pb push_back
#define ordered_set tree<pair<ll, ll>, null_type, less<pair<ll, ll>>, rb_tree_tag, tree_order_statistics_node_update>
#define MOD 111539786
#define vv vector<vector<ll>>
#define pv vector<pair<ll, ll>>
struct noob{
ll cnt;
pv pref, suf;
noob(pv &pref, pv &suf) : pref(pref), suf(suf) {}
noob (ll a) {
pref.push_back({a, 1});
suf.push_back({a, 1});
cnt = (a != 1);
}
noob() {
cnt = 0;
}
};
noob combine(noob &a, noob &b){
noob c(a.pref, b.suf);
f(i, a.suf.size()) {
if (c.suf.size()) {
ll val = __gcd<ll>(c.suf.back().fi, a.suf[i].fi);
if (val == c.suf.back().fi) c.suf.back().se += a.suf[i].se;
else c.suf.push_back({val, a.suf[i].se});
}
else c.suf.push_back(a.suf[i]);
}
f(i, b.pref.size()) {
if (c.pref.size()) {
ll val = __gcd<ll>(c.pref.back().fi, b.pref[i].fi);
if (val == c.pref.back().fi) c.pref.back().se += b.pref[i].se;
else c.pref.push_back({val, b.pref[i].se});
}
else c.pref.push_back(b.pref[i]);
}
c.cnt = b.cnt + a.cnt;
ll j = b.pref.size() - 1;
ll sum = 0;
f(j, b.pref.size()) {
sum += b.pref[j].se;
}
f(i, a.suf.size()) {
while (j >= 0) {
ll val = __gcd<ll>(b.pref[j].fi, a.suf[i].fi);
if (val == 1) {
sum -= b.pref[j].se;
j--;
}
else break;
}
c.cnt += a.suf[i].se * sum;
}
return c;
}
ll arr[100000], n ,q;
noob st[200002];
void build() {
fd(i, n - 1, 1) {
st[i] = combine(st[i << 1], st[i << 1 | 1]);
}
}
ll query(ll l, ll r) {
noob resl, resr;
for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
if (l & 1) resl = combine(resl, st[l++]);
if (r & 1) resr = combine(st[--r], resr);
}
return combine(resl, resr).cnt;
}
void update(ll i, ll x) {
for (st[i += n] = noob(x); i >>= 1;) {
st[i] = combine(st[i<<1],st[i<<1|1]);
}
}
void solve() {
cin >> n >> q;
f(i, n) {
cin >> arr[i];
st[i + n] = noob(arr[i]);
}
build();
ll a, b, c;
f(i, q) {
cin >> a >> b >> c;
if (a == 1) update(b - 1, c);
else cout << query(b - 1, c) << '\n';
}
}
int main()
{
//freopen("SEQUENCE.INP", "r" ,stdin); freopen("SEQUENCE.OUT", "w", stdout);
std::ios_base::sync_with_stdio(0);
std::cin.tie(0);
long long test = 1;
//cin >> test;
for (int i = 0; i < test; i += 1)
{
solve();
}
return 0;
}
Compilation message
garaza.cpp: In function 'noob combine(noob&, noob&)':
garaza.cpp:35:34: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
35 | #define f(i, n) for (ll i = 0; i < n; i += 1)
......
62 | f(i, a.suf.size()) {
| ~~~~~~~~~~~~~~~
garaza.cpp:62:5: note: in expansion of macro 'f'
62 | f(i, a.suf.size()) {
| ^
garaza.cpp:35:34: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
35 | #define f(i, n) for (ll i = 0; i < n; i += 1)
......
71 | f(i, b.pref.size()) {
| ~~~~~~~~~~~~~~~~
garaza.cpp:71:5: note: in expansion of macro 'f'
71 | f(i, b.pref.size()) {
| ^
garaza.cpp:35:34: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
35 | #define f(i, n) for (ll i = 0; i < n; i += 1)
......
82 | f(j, b.pref.size()) {
| ~~~~~~~~~~~~~~~~
garaza.cpp:82:5: note: in expansion of macro 'f'
82 | f(j, b.pref.size()) {
| ^
garaza.cpp:35:34: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
35 | #define f(i, n) for (ll i = 0; i < n; i += 1)
......
85 | f(i, a.suf.size()) {
| ~~~~~~~~~~~~~~~
garaza.cpp:85:5: note: in expansion of macro 'f'
85 | f(i, a.suf.size()) {
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
11476 KB |
Output is correct |
| 2 |
Correct |
14 ms |
11940 KB |
Output is correct |
| 3 |
Correct |
21 ms |
12348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
92 ms |
15684 KB |
Output is correct |
| 2 |
Correct |
120 ms |
17776 KB |
Output is correct |
| 3 |
Correct |
117 ms |
17232 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
230 ms |
21980 KB |
Output is correct |
| 2 |
Correct |
291 ms |
22220 KB |
Output is correct |
| 3 |
Correct |
273 ms |
23376 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
490 ms |
33052 KB |
Output is correct |
| 2 |
Correct |
531 ms |
33124 KB |
Output is correct |
| 3 |
Correct |
495 ms |
31408 KB |
Output is correct |
