| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 240050 | Vimmer | Garaža (COCI17_garaza) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("-O3")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("fast-math")
//#pragma GCC optimize("no-stack-protector")
#define F first
#define S second
#define sz(x) int(x.size())
#define pb push_back
#define N 101001
#define M ll(1e9 + 7)
#define inf 1e9 + 1e9
using namespace std;
//using namespace __gnu_pbds;
typedef long double ld;
typedef long long ll;
typedef short int si;
typedef array <int, 3> a3;
//typedef tree <int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
struct st
{
vector <pair <ll, ll> > pr, sf;
ll ans;
};
int n, q, a[N];
st t[N * 4];
st combine(st a, st b)
{
st res;
res.pr = a.pr;
for (int i = 0; i < sz(b.pr); i++)
{
pair <int, int> cur = b.pr[i];
int g = __gcd(res.pr.back().F, cur.F);
if (g == res.pr.back().F) res.pr.back().S += cur.S;
else res.pr.pb({g, cur.S});
}
res.sf = b.sf;
for (int i = sz(a.sf) - 1; i >= 0; i--)
{
pair <int, int> cur = a.sf[i];
int g = __gcd(res.sf.back().F, cur.F);
if (g == res.sf.back().F) res.sf.back().S += cur.S;
else res.sf.pb({g, cur.S});
}
res.ans = a.ans + b.ans;
int pr[sz(b.pr)];
pr[0] = b.pr[0].S;
for (int i = 1; i < sz(b.pr); i++) pr[i] = pr[i - 1] + b.pr[i].S;
int j = sz(b.pr) - 1;
for (int i = 0; i < sz(a.sf); i++)
{
pair <int, int> cur = a.sf[i];
while (1)
{
if (j == -1) break;
int g = __gcd(cur.F, b.pr[j].F);
if (g == 1) j--;
else break;
}
if (j == -1) break;
res.ans += ll(pr[j]) * ll(cur.S);
}
return res;
}
void build(int v, int tl, int tr)
{
if (tl == tr)
{
t[v].ans = int(a[tl] > 1);
t[v].pr.pb({a[tl], 1});
t[v].sf.pb({a[tl], 1});
return;
}
int md = (tl + tr) >> 1;
build(v + v, tl, md);
build(v + v + 1, md + 1, tr);
t[v] = combine(t[v + v], t[v + v + 1]);
}
void upd(int v, int tl, int tr, int pos)
{
if (tl == tr)
{
t[v].ans = bool(a[tl] > 1);
t[v].pr.clear(); t[v].sf.clear();
t[v].pr.pb({a[tl], 1});
t[v].sf.pb({a[tl], 1});
return;
}
int md = (tl + tr) >> 1;
if (pos <= md) upd(v + v, tl, md, pos);
else upd(v + v + 1, md + 1, tr, pos);
t[v] = combine(t[v + v], t[v + v + 1]);
}
st calc(int v, int tl, int tr, int l, int r)
{
if (tl == tr) return t[v];
int md = (tl + tr) >> 1;
if (r <= md) return calc(v + v, tl, md, l, r);
if (md + 1 <= l) return calc(v + v + 1, md + 1, tr, l, r);
return combine(calc(v + v, tl, md, l, r), calc(v + v + 1, md + 1, tr, l, r));
}
int main()
{
//freopen("input.txt", "r", stdin); //freopen("output4.txt", "w", stdout);
ios_base::sync_with_stdio(0); istream::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n >> q;
for (int i = 0; i < n; i++) cin >> a[i];
build(1, 0, n - 1);
for ( ;q > 0; q--)
{
int tp, l, r;
cin >> tp >> l >> r;
if (tp == 2) cout << calc(1, 0, n - 1, l - 1, r - 1).ans << '\n';
else {l--; a[l] = r; upd(1, 0, n - 1, l); }
}
}