#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define sz(x) int((x).size())
#define fi first
#define se second
typedef long long ll;
typedef pair<int, int> ii;
template<class X, class Y>
inline bool maximize(X &x, const Y &y) {return (x < y ? x = y, 1 : 0);}
template<class X, class Y>
inline bool minimize(X &x, const Y &y) {return (x > y ? x = y, 1 : 0);}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int Random(int l, int r) {
return uniform_int_distribution<int>(l, r)(rng);
}
const int MAXN = 100005;
struct Node {
ll sum;
int minv, lz;
} seg2[4 * MAXN];
int a[MAXN], b[MAXN], seg[4 * MAXN], posInTree[MAXN], nArr, numQuery;
void build(int id, int l, int r) {
if(l == r) {
posInTree[l] = id;
seg[id] = a[l];
seg2[id] = {b[l], b[l], -1};
return;
}
int mid = (l + r) >> 1;
build(id << 1, l, mid);
build(id << 1 | 1, mid + 1, r);
seg[id] = __gcd(seg[id << 1], seg[id << 1 | 1]);
seg2[id] = {seg2[id << 1].sum + seg2[id << 1 | 1].sum, min(seg2[id << 1].minv, seg2[id << 1 | 1].minv), -1};
}
void update1(int pos, int val) {
int id(posInTree[pos]);
seg[id] = val;
while(id > 1) {
id >>= 1;
seg[id] = __gcd(seg[id << 1], seg[id << 1 | 1]);
}
}
int query1(int id, int l, int r, int u, int v) {
if(v < l || u > r)
return 0;
if(u <= l && r <= v)
return seg[id];
int mid = (l + r) >> 1;
return __gcd(query1(id << 1, l, mid, u, v), query1(id << 1 | 1, mid + 1, r, u, v));
}
void inline pushDown(int id, int l, int r) {
int &lz(seg2[id].lz), mid = (l + r) >> 1;
seg2[id << 1] = {1LL * (mid - l + 1) * lz, lz, lz};
seg2[id << 1 | 1] = {1LL * (r - mid) * lz, lz, lz};
lz = -1;
}
void update2(int id, int l, int r, int u, int v, int k) {
if(v < l || u > r)
return;
if(u <= l && r <= v) {
seg2[id] = {1LL * (r - l + 1) * k, k, k};
return;
}
if(seg2[id].lz != -1)
pushDown(id, l, r);
int mid = (l + r) >> 1;
update2(id << 1, l, mid, u, v, k);
update2(id << 1 | 1, mid + 1, r, u, v, k);
seg2[id] = {seg2[id << 1].sum + seg2[id << 1 | 1].sum, min(seg2[id << 1].minv, seg2[id << 1 | 1].minv), -1};
}
ll query2(int id, int l, int r, int u, int v) {
if(v < l || u > r)
return 0;
if(u <= l && r <= v)
return seg2[id].sum;
if(seg2[id].lz != -1)
pushDown(id, l, r);
int mid = (l + r) >> 1;
return query2(id << 1, l, mid, u, v) + query2(id << 1 | 1, mid + 1, r, u, v);
}
int walkOnSeg(int id, int l, int r, int u, int v, int k) {
if(v < l || u > r)
return v + 1;
if(u <= l && r <= v) {
while(l < r) {
if(seg2[id].lz != -1)
pushDown(id, l, r);
int mid = (l + r) >> 1;
if(seg2[id << 1 | 1].minv >= k) {
id = id << 1;
r = mid;
} else {
id = id << 1 | 1;
l = mid + 1;
}
}
return (seg2[id].minv >= k) ? l : l + 1;
}
if(seg2[id].lz != -1)
pushDown(id, l, r);
int mid = (l + r) >> 1;
int qr = walkOnSeg(id << 1 | 1, mid + 1, r, u, v, k);
if(qr > mid + 1)
return qr;
return min(qr, walkOnSeg(id << 1, l, mid, u, v, k));
}
inline ll C2(int n) {
return 1LL * n * (n + 1) / 2;
}
void process() {
cin >> nArr >> numQuery;
for (int i = 1; i <= nArr; ++i) {
cin >> a[i];
}
build(1, 1, nArr);
for (int i = 1; i <= nArr; ++i) {
b[i] = i - 1;
if(a[i] == 1)
continue;
int l(i + 1), r(nArr), opt(i);
while(l <= r) {
int mid = (l + r) >> 1;
if(query1(1, 1, nArr, i, mid) > 1) {
opt = mid;
l = mid + 1;
} else {
r = mid - 1;
}
}
b[i] = opt;
}
build(1, 1, nArr);
for (int t = 0; t < numQuery; ++t) {
int type, L, R, x;
cin >> type >> L >> R;
if(type == 1) {
update1(L, R);
a[(x = L)] = R;
int gcdNow(a[x]);
while(x > 0 && gcdNow > 1) {
int l(1), r(x - 1), opt(x);
while(l <= r) {
int mid = (l + r) >> 1;
if(query1(1, 1, nArr, mid, x) == gcdNow) {
opt = mid;
r = mid - 1;
} else {
l = mid + 1;
}
}
int tmp(opt);
l = L + 1, r = nArr, opt = L;
while(l <= r) {
int mid = (l + r) >> 1;
if(query1(1, 1, nArr, tmp, mid) > 1) {
opt = mid;
l = mid + 1;
} else {
r = mid - 1;
}
}
update2(1, 1, nArr, tmp, x, opt);
//cout << '.' << tmp << ' ' << x << ' ' << opt << '\n';
x = tmp - 1;
if(x > 0)
gcdNow = __gcd(gcdNow, a[x]);
}
if(x > 0) {
int pos = walkOnSeg(1, 1, nArr, 1, x, L);
//cout << '.' << pos << ' ' << x << ' ' << L - 1 << '\n';
if(pos <= x)
update2(1, 1, nArr, pos, x, L - 1);
}
} else {
ll result(0);
int pos = walkOnSeg(1, 1, nArr, L, R, R);
//cout << L << ' ' << R << ' ' << pos << '\n';
if(pos <= R)
result += 1LL * (R - pos + 1) * (R + 1) - (C2(R) - C2(pos - 1));
if(L < pos)
result += query2(1, 1, nArr, L, pos - 1) - (C2(pos - 1) - C2(L - 1)) + (pos - L);
cout << result << '\n';
}
}
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
process();
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
340 KB |
Output is correct |
| 2 |
Correct |
26 ms |
600 KB |
Output is correct |
| 3 |
Correct |
213 ms |
852 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1572 ms |
2348 KB |
Output is correct |
| 2 |
Correct |
224 ms |
2784 KB |
Output is correct |
| 3 |
Correct |
259 ms |
2760 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1273 ms |
4640 KB |
Output is correct |
| 2 |
Execution timed out |
4057 ms |
5108 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1153 ms |
9432 KB |
Output is correct |
| 2 |
Execution timed out |
4037 ms |
7800 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
