結果
問題 | No.880 Yet Another Segment Tree Problem |
ユーザー |
![]() |
提出日時 | 2019-09-07 12:24:20 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
RE
|
実行時間 | - |
コード長 | 5,036 bytes |
コンパイル時間 | 1,185 ms |
コンパイル使用メモリ | 96,624 KB |
実行使用メモリ | 6,948 KB |
最終ジャッジ日時 | 2024-06-26 08:07:28 |
合計ジャッジ時間 | 8,276 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 10 RE * 27 |
ソースコード
#include<iostream>#include<string>#include<vector>#include<queue>#include<stack>#include<map>#include<set>#include<algorithm>#include<functional>#include<cstdio>#include<cstdlib>#include<cmath>#include<cassert>#include<ctime>using namespace std;#define mind(a,b) (a>b?b:a)#define maxd(a,b) (a>b?a:b)#define absd(x) (x<0?-(x):x)#define pow2(x) ((x)*(x))#define rep(i,n) for(int i=0; i<n; ++i)#define repr(i,n) for(int i=n-1; i>=0; --i)#define repl(i,s,n) for(int i=s; i<=n; ++i)#define replr(i,s,n) for(int i=n; i>=s; --i)#define repf(i,s,n,j) for(int i=s; i<=n; i+=j)#define repe(e,obj) for(auto e : obj)#define SP << " " <<#define COL << " : " <<#define COM << ", " <<#define ARR << " -> " <<#define PNT(STR) cout << STR << endl#define POS(X,Y) "(" << X << ", " << Y << ")"#define DEB(A) " (" << #A << ") " << A#define DEBREP(i,n,val) for(int i=0; i<n; ++i) cout << val << " "; cout << endl#define ALL(V) (V).begin(), (V).end()#define INF 1000000007#define INFLL 1000000000000000007LL#define EPS 1e-9typedef unsigned int uint;typedef unsigned long ulong;typedef unsigned long long ull;typedef long long ll;typedef long double ld;#define P_TYPE lltypedef pair<P_TYPE, P_TYPE> P;typedef pair<P, P_TYPE> PI;typedef pair<P_TYPE, P> IP;typedef pair<P, P> PP;typedef priority_queue<P, vector<P>, greater<P> > pvqueue;#define N (1 << 10)class SegmentTree {static const ll inf = 1e18;struct Node {ll max_v, min_v;ll lazy, cnt, sum;bool has;void init(ll x) {max_v = min_v = sum = x;cnt = 1;}void init_empty() {max_v = -inf; min_v = inf;sum = cnt = 0;}inline void update_value(ll x) {lazy = x;sum = x * cnt;max_v = min_v = x;has = true;}inline void propagate(Node &left, Node &right) {if(!has) return;left.update_value(lazy);right.update_value(lazy);has = false;}inline void build(Node &left, Node &right) {max_v = max(left.max_v, right.max_v);min_v = min(left.min_v, right.min_v);sum = left.sum + right.sum;cnt = left.cnt + right.cnt;}} nds[2*N];int n0, n;ll gcd(ll m, ll n) {ll r = m % n;return r ? gcd(n, r) : n;}void _set(ll x, int a, int b, int k, int l, int r) {Node &nd = nds[k];if(k < n0-1) nd.propagate(nds[2*k+1], nds[2*k+2]);if(b <= l || r <= a) {return;}if(a <= l && r <= b) {nd.update_value(x);return;}_set(x, a, b, 2*k+1, l, (l+r)/2);_set(x, a, b, 2*k+2, (l+r)/2, r);if(k < n0-1) nd.build(nds[2*k+1], nds[2*k+2]);}void _gcd(ll x, int a, int b, int k, int l, int r) {Node &nd = nds[k];if(k < n0-1) nd.propagate(nds[2*k+1], nds[2*k+2]);if(b <= l || r <= a) {return;}if(a <= l && r <= b && nd.max_v == nd.min_v) {nd.update_value(gcd(x, nd.max_v));return;}_gcd(x, a, b, 2*k+1, l, (l+r)/2);_gcd(x, a, b, 2*k+2, (l+r)/2, r);if(k < n0-1) nd.build(nds[2*k+1], nds[2*k+2]);}ll _query_sum(int a, int b, int k, int l, int r) {Node &nd = nds[k];if(k < n0-1) nd.propagate(nds[2*k+1], nds[2*k+2]);if(b <= l || r <= a) {return 0;}if(a <= l && r <= b) {return nd.sum;}ll lv = _query_sum(a, b, 2*k+1, l, (l+r)/2);ll rv = _query_sum(a, b, 2*k+2, (l+r)/2, r);if(k < n0-1) nd.build(nds[2*k+1], nds[2*k+2]);return lv + rv;}ll _query_max(int a, int b, int k, int l, int r) {Node &nd = nds[k];if(k < n0-1) nd.propagate(nds[2*k+1], nds[2*k+2]);if(b <= l || r <= a) {return -inf;}if(a <= l && r <= b) {return nd.max_v;}ll lv = _query_max(a, b, 2*k+1, l, (l+r)/2);ll rv = _query_max(a, b, 2*k+2, (l+r)/2, r);if(k < n0-1) nd.build(nds[2*k+1], nds[2*k+2]);return max(lv, rv);}public:SegmentTree(int n, ll *a) {n0 = 1;while(n0 < n) n0 <<= 1;for(int i=0; i<n; ++i) nds[i+n0-1].init(a[i]);for(int i=n; i<n0; ++i) nds[i+n0-1].init_empty();for(int i=0; i<2*n0-1; ++i) nds[i].lazy = 0, nds[i].has = false;for(int i=n0-2; i>=0; --i) {nds[i].build(nds[2*i+1], nds[2*i+2]);}}void set(int l, int r, ll x) {_set(x, l, r, 0, 0, n0);}void gcd(int l, int r, ll x) {_gcd(x, l, r, 0, 0, n0);}ll query_sum(int l, int r) {return _query_sum(l, r, 0, 0, n0);}ll query_max(int l, int r) {return _query_max(l, r, 0, 0, n0);}};ll a[N];int main() {int n, q;cin >> n >> q;rep(i, n) cin >> a[i];SegmentTree st(n, a);while(q--) {int t, l, r; ll x;cin >> t >> l >> r;switch(t) {case 1:cin >> x;st.set(l-1, r, x);break;case 2:cin >> x;st.gcd(l-1, r, x);break;case 3:cout << st.query_max(l-1, r) << endl;break;case 4:cout << st.query_sum(l-1, r) << endl;break;}}return 0;}