結果
問題 | No.880 Yet Another Segment Tree Problem |
ユーザー |
![]() |
提出日時 | 2019-09-07 01:54:38 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 756 ms / 5,000 ms |
コード長 | 3,897 bytes |
コンパイル時間 | 1,489 ms |
コンパイル使用メモリ | 118,872 KB |
実行使用メモリ | 11,648 KB |
最終ジャッジ日時 | 2024-09-22 19:36:13 |
合計ジャッジ時間 | 15,293 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 37 |
ソースコード
// includes {{{ #include<iostream> #include<iomanip> #include<algorithm> #include<vector> #include<stack> #include<queue> #include<map> #include<set> #include<tuple> #include<cmath> #include<random> #include<cassert> #include<bitset> #include<cstdlib> // #include<deque> // #include<multiset> // #include<cstring> // #include<bits/stdc++.h> // }}} using namespace std; using ll = long long; constexpr ll inf = 1e9 + 1; /// --- math {{{ /// ll gcd(ll a, ll b) { return b == 0 ? a : gcd(b, a % b); } ll lcm(ll a, ll b) { return min(a / gcd(a, b) * b, inf); } ll extgcd(ll a, ll b, ll &x, ll &y) { ll d; return b == 0 ? (x = a < 0 ? -1 : 1, y = 0, a < 0 ? -a : a) : (d = extgcd(b, a % b, y, x), y -= a / b * x, d); } ll modinv(ll a, ll mod) { ll x, y; extgcd(a, mod, x, y); if(x < 0) x += mod; return x; } ll modpow(ll a, ll b, ll mod) { ll r = 1; a %= mod; while(b) { if(b & 1) r = r * a % mod; a = a * a % mod; b >>= 1; } return r; } /// }}}--- /// constexpr int N = 1e5; struct Seg { vector<ll> setL; vector<ll> sum; vector<ll> ma; vector<ll> LCM; vector<bool> same; int n; Seg(int t) { n = 1; while(n < t) n <<= 1; setL.resize(2 * n, 0); sum.resize(2 * n, 1); ma.resize(2 * n, 1); LCM.resize(2 * n, 1); same.resize(2 * n, 1); } void eval(int k, int l, int r) { if(r - l > 1) { if(setL[k]) { setL[k * 2 + 1] = setL[k]; setL[k * 2 + 2] = setL[k]; } } if(setL[k]) { sum[k] = setL[k] * (r - l); ma[k] = setL[k]; LCM[k] = setL[k]; same[k] = 1; setL[k] = 0; } } void update(int k, int l, int r) { assert(r - l > 1); sum[k] = sum[k * 2 + 1] + sum[k * 2 + 2]; ma[k] = ::max(ma[k * 2 + 1], ma[k * 2 + 2]); LCM[k] = ::lcm(LCM[k * 2 + 1], LCM[k * 2 + 2]); same[k] = same[k * 2 + 1] && same[k * 2 + 2] && ma[k * 2 + 1] == ma[k * 2 + 2]; } void set(int a, int b, ll x, int k = 0, int l = 0, int r = -1) { if(r == -1) r = n; eval(k, l, r); if(b <= l || r <= a) return; if(a <= l && r <= b) { setL[k] = x; eval(k, l, r); return; } set(a, b, x, k * 2 + 1, l, (l + r) >> 1); set(a, b, x, k * 2 + 2, (l + r) >> 1, r); update(k, l, r); } void gcd(int a, int b, ll x, int k = 0, int l = 0, int r = -1) { if(r == -1) r = n; eval(k, l, r); if(x % LCM[k] == 0) return; if(b <= l || r <= a) return; if(a <= l && r <= b) { if(same[k]) { setL[k] = ::gcd(x, ma[k]); eval(k, l, r); return; } } gcd(a, b, x, k * 2 + 1, l, (l + r) >> 1); gcd(a, b, x, k * 2 + 2, (l + r) >> 1, r); update(k, l, r); } ll MAX(int a, int b, int k = 0, int l = 0, int r = -1) { if(r == -1) r = n; eval(k, l, r); if(b <= l || r <= a) return 0; if(a <= l && r <= b) return ma[k]; ll res = max( MAX(a, b, k * 2 + 1, l, (l + r) >> 1), MAX(a, b, k * 2 + 2, (l + r) >> 1, r) ); update(k, l, r); return res; } ll SUM(int a, int b, int k = 0, int l = 0, int r = -1) { if(r == -1) r = n; eval(k, l, r); if(b <= l || r <= a) return 0; if(a <= l && r <= b) return sum[k]; ll res = SUM(a, b, k * 2 + 1, l, (l + r) >> 1) + SUM(a, b, k * 2 + 2, (l + r) >> 1, r); update(k, l, r); return res; } }; int n, q; int main() { std::ios::sync_with_stdio(false), std::cin.tie(0); cin >> n >> q; Seg seg(n); for(int i = 0; i < n; i++) { int a; cin >> a; seg.set(i, i + 1, a); } for(int i = 0; i < q; i++) { int t, l, r; int x; cin >> t >> l >> r; l--; if(t == 1) { cin >> x; seg.set(l, r, x); } else if(t == 2) { cin >> x; seg.gcd(l, r, x); } else if(t == 3) { cout << seg.MAX(l, r) << "\n"; } else { cout << seg.SUM(l, r) << "\n"; } } return 0; }