// compile with -O2 -std=gnu++17 #include <bits/stdc++.h> using namespace std; using ll = long long; using pii = pair<int,int>; const ll mod = 1000000007LL; const long double THRESH = 1e9L; // threshold used in original code // fast powmod ll modpow(ll a, ll e) { ll r = 1 % mod; a %= mod; while (e) { if (e & 1) r = (r * a) % mod; a = (a * a) % mod; e >>= 1; } return r; } ll invmod(ll a){ return modpow((a%mod+mod)%mod, mod-2); } // Fenwick (BIT) for multiplicative prefix product modulo `mod`. struct Fenwick { int n; vector<ll> bit; Fenwick() : n(0) {} Fenwick(int _n){ init(_n); } void init(int _n){ n = _n; bit.assign(n+1, 1); } // multiply index i by val (mod) void mul_point(int i, ll val){ while(i <= n){ bit[i] = (bit[i] * val) % mod; i += i & -i; } } // prefix product 1..i ll prefix(int i) const { ll res = 1; while(i > 0){ res = (res * bit[i]) % mod; i -= i & -i; } return res; } // range product l..r ll range(int l,int r) const { if(l>r) return 1; ll a = prefix(r); ll b = prefix(l-1); return (a * invmod(b)) % mod; } }; // iterative segment tree for range max, point update struct SegMax { int n; int size; vector<int> seg; SegMax(){} void init(int _n){ n = _n; size = 1; while(size < n) size <<= 1; seg.assign(2*size, 0); } void set_point(int pos, int val){ // pos in [1..n] int i = pos - 1 + size; seg[i] = val; for(i >>= 1; i; i >>= 1) seg[i] = max(seg[2*i], seg[2*i+1]); } int range_max(int l,int r){ // inclusive, 1..n if(l>r) return 0; int L = l - 1 + size, R = r - 1 + size; int ans = 0; while(L <= R){ if(L & 1) ans = max(ans, seg[L++]); if(!(R & 1)) ans = max(ans, seg[R--]); L >>= 1; R >>= 1; } return ans; } }; static int N_global = 0; static vector<int> Xarr, Yarr; // 0..N static Fenwick fen; static SegMax segy; static set<int> special; // indices i where X[i] > 1, plus sentinel 0 static const ll SENTINEL_X0 = 1000000000LL; // same as 1e9 from your code // get segment end for special index s: next(s) - 1, or N_global if none inline int seg_end_of(int s){ auto it = special.upper_bound(s); if(it == special.end()) return N_global; return (*it) - 1; } // compute answer following the same logic as original code int compute_answer(){ // collect suffix of special indices starting from largest until product >= 1e9 deque<pair<int,int>> a; // (startIndex, endIndex) __int128 tem = 1; for(auto it = special.rbegin(); it != special.rend(); ++it){ int s = *it; int r = seg_end_of(s); a.emplace_front(s, r); tem *= (__int128) Xarr[s]; if(tem >= (__int128)1000000000LL) break; } // special-case matching original: // if the first picked segment starts at 0 (sentinel), temporarily remove it from consideration long long ans1 = 0; __int128 intem = tem; if(!a.empty() && a.front().first == 0){ // divide out sentinel contribution tem /= (__int128)Xarr[0]; // Xarr[0] = 1e9 sentinel intem /= (__int128)Xarr[0]; if(tem < (__int128)1000000000LL){ // ans1 = ry.mx(1,n) in your code ans1 = segy.range_max(1, N_global); } // remove sentinel from deque (original code popped it) a.pop_front(); } if(a.empty()){ // nothing chosen: return overall max y return segy.range_max(1, N_global) % (int)mod; } // compute ma = max over selected segments of (product_of_selected_specials_prefix * maxY_in_segment) __int128 prodprefix = 1; __int128 ma128 = 0; for(auto &pr : a){ int s = pr.first, r = pr.second; prodprefix *= (__int128) Xarr[s]; int localMaxY = 0; if(s == 0){ // should not happen here (we popped sentinel); but safe fallback localMaxY = segy.range_max(1, N_global); } else { localMaxY = segy.range_max(s, r); } __int128 candidate = prodprefix * (__int128)localMaxY; if(candidate > ma128) ma128 = candidate; } // multiply by product of x's on left of first selected special: rx.mul(1, a[0].fi-1) int firstSpecial = a.front().first; ll leftProdMod = fen.range(1, max(0, firstSpecial - 1)); // incorporate ans1 if applicable (original logic took max with ma after mod) ll ma_mod = (ll)( ( (long long)(ma128 % (__int128)mod) ) % mod ); if(intem < (__int128)1000000000LL){ ma_mod = max(ma_mod, (ll)ans1); // ans1 already fits in int } ll result = (ma_mod * leftProdMod) % mod; return (int) result; } // API functions (match original names/behaviour) int init(int N, int X[], int Y[]){ N_global = N; Xarr.assign(N+1, 1); Yarr.assign(N+1, 0); // index 0 sentinel Xarr[0] = (int)SENTINEL_X0; // Fenwick only stores indices 1..N fen.init(N); segy.init(N); special.clear(); special.insert(0); // sentinel // fill arrays and structures for(int i=1;i<=N;i++){ Xarr[i] = X[i-1]; Yarr[i] = Y[i-1]; // fenwick multiply by X[i] fen.mul_point(i, (Xarr[i] % mod + mod) % mod); // segtree for Y segy.set_point(i, Yarr[i]); if(Xarr[i] > 1) special.insert(i); } // answer return compute_answer(); } int updateX(int idx0, int v){ // idx0 is 0-based int i = idx0 + 1; int old = Xarr[i]; if(old == v) return compute_answer(); // update fenwick: multiply index i by (v * inv(old)) ll mulval = ( (v % mod + mod) % mod ) * invmod( (old % mod + mod) % mod ) % mod; fen.mul_point(i, mulval); Xarr[i] = v; // maintain special set bool wasSpecial = (old > 1); bool nowSpecial = (v > 1); if(wasSpecial && !nowSpecial){ special.erase(i); } else if(!wasSpecial && nowSpecial){ special.insert(i); } return compute_answer(); } int updateY(int idx0, int v){ int i = idx0 + 1; Yarr[i] = v; segy.set_point(i, v); return compute_answer(); }