| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1198668 | matus192 | 말 (IOI15_horses) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef vector<int> vi;
typedef vector<long long> vll;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> oset;
#define REP(i, a, b) for (ll i = (a); i < (b); i++)
#define FOR(i, x) for (auto &i : x)
#define ff first
#define ss second
#define pb push_back
#define all(x) x.begin(), x.end()
#define IMAX INT_MAX
#define IMIN INT_MIN
#define LMIN LONG_LONG_MIN
#define LMAX LONG_LONG_MAX
#define MOD 1000000007
#define SIR 1000000009
ll n;
vll zmena, cena;
ll power(ll a, ll e) {
if (e == 0) return 1;
ll res = power(a, e / 2);
res = (res * res) % MOD;
if (e % 2 == 1) {
res = (res * a) % MOD;
}
return res;
}
ll inv(ll a) {
return power(a, MOD - 2);
}
struct Node {
ll l, r;
Node *lson, *rson;
ll lazy, val;
long double LAZY, VAL;
Node(ll vl, ll vr, vector<pair<long double, ll>> &init) {
l = vl;
r = vr;
lazy = 1;
LAZY = 0;
if (l + 1 == r) {
lson = NULL;
rson = NULL;
val = init[l].ss;
VAL = init[l].ff;
} else {
lson = new Node(vl, (vl + vr) / 2, init);
rson = new Node((vl + vr) / 2, vr, init);
if (lson->VAL > rson->VAL) {
VAL = lson->VAL;
val = lson->val;
} else {
VAL = rson->VAL;
val = rson->val;
}
}
}
void remove_lazy() {
if (l + 1 != r) {
lson->lazy = (lson->lazy * lazy) % MOD;
rson->lazy = (rson->lazy * lazy) % MOD;
lson->val = (lson->val * lazy) % MOD;
rson->val = (rson->val * lazy) % MOD;
lson->LAZY = (lson->LAZY + LAZY);
rson->LAZY = (rson->LAZY + LAZY);
lson->VAL = (lson->VAL + LAZY);
rson->VAL = (rson->VAL + LAZY);
}
lazy = 1;
LAZY = 0;
}
void update(ll ql, ll qr, ll inc, long double INC) {
if (qr <= l || ql >= r) return;
if (ql <= l && qr >= r) {
lazy = (lazy * inc) % MOD;
val = (val * inc) % MOD;
LAZY = (LAZY + INC);
VAL = (VAL + INC);
return;
}
remove_lazy();
lson->update(ql, qr, inc, INC);
rson->update(ql, qr, inc, INC);
if (lson->VAL > rson->VAL) {
VAL = lson->VAL;
val = lson->val;
} else {
VAL = rson->VAL;
val = rson->val;
}
return;
}
pair<long double, ll> find(ll ql, ll qr) {
if (qr <= l || ql >= r) return {IMIN, LMIN};
if (ql <= l && qr >= r) return {VAL, val};
remove_lazy();
auto lans = lson->find(ql, qr);
auto rans = rson->find(ql, qr);
if (lans.ff > rans.ff) {
return lans;
} else {
return rans;
}
}
};
int main() {
cin >> n;
zmena.resize(n);
cena.resize(n);
REP(i, 0, n) {
cin >> zmena[i];
}
REP(i, 0, n) {
cin >> cena[i];
}
ll akt = 1;
long double AKT = 0;
vector<pair<long double, ll>> init(n);
REP(i, 0, n) {
long double zmn = zmena[i], cna = cena[i];
akt = (akt * zmena[i]) % MOD;
AKT += log(zmn);
ll cn = (akt * cena[i]) % MOD;
long double CN = AKT + log(cna);
init[i] = {CN, cn};
}
Node root(0, n, init);
cout << root.find(0, n).ss << '\n';
ll q;
cin >> q;
REP(i, 0, q) {
ll t;
cin >> t;
ll x, nw;
cin >> x >> nw;
if (t == 1) {
long double zmn = zmena[x];
ll in = inv(zmena[x]);
long double IN = -log(zmn);
root.update(x, n+50, in, IN);
zmena[x] = nw;
long double NW = nw;
NW = log(NW);
root.update(x, n+50, nw, NW);
} else {
long double cna = cena[x];
ll in = inv(cena[x]);
long double IN = -log(cna);
root.update(x, x+1, in, IN);
cena[x] = nw;
long double NW = nw;
NW = log(NW);
root.update(x, x+1, nw, NW);
}
cout << root.find(0, n).ss << '\n';
}
return 0;
}