[ABC368] G - Add and Multiply Queries
[Q] G - Add and Multiply Queries
日立ヴァンタラプログラミングコンテスト2024。
Fで大量にWAを出して落ち込んでいる最中、EかGのどちらに進むか悩む。Eに行ってしまう。
Gがカスタマイズを要するセグ木に見えてひよったからだ。そうして大敗を喫する。
実際はBITとsetで事足りるのに。。
考察
1. クエリの回答が1e18までしか来ない。
2. つまり、配列Bに1,1,1,1,1…という箇所がたくさんあるはず。その箇所のAを累積和をとっておけばよさそう。BITで事足りる
3. 配列Bの中で値が2以上のindexを取得できれば嬉しい。セグ木でもいいけど、setでいい。
横着してlower_boundはダメ。sort済み配列にしか使用できない関数だ。当たり前のことなのになんか忘れてしまっていた。
sort済みでない配列にlower_bound(upper_bound)をすると何が得られる？
細かい2点。
4. v = 0から始まるので、最初はA[L]を必ずとればいい。
5. Bの値が2以上のindex_iは、v = max(v + A[i], v * B[i]) で大きいほうをとればいい。
これを実装する。
実装
template<ll BT>
struct Bit
{
ll dat[BT+10]{};
void add(ll i, ll x){
++i;
for(; i<BT; i += i&-i) dat[i] += x;
}
// iの値を取り出したいときはsum(i)
ll sum(ll i){ // [0, i]
if (i<0) return 0;
if (i>=BT-1) i = BT-2;
++i;
ll res = 0;
for(; i>0; i -= i&-i) res += dat[i];
return res;
}
ll rangesum(ll L, ll R){ // [L, R)
return sum(R - 1) - sum(L - 1);
}
};
int main(){
cincout();
ll N;
cin >> N;
Bit<100010> bit;
vector<ll> A(N), B(N);
set<ll> S;
rep(i, N){
cin >> A[i];
bit.add(i, A[i]);
}
rep(i, N){
cin >> B[i];
if (B[i] > 1) S.insert(i); // Bが2以上の時掛け算を採用する候補になる。Aが1e9のときはAをとるかもね
}
S.insert(N); // 番兵node
ll Q;
cin >> Q;
while(Q--){
ll type;
cin >> type;
if (type == 1){
ll i, x;
cin >> i >> x;
--i;
bit.add(i, x - A[i]);
A[i] = x;
}
else if (type == 2){
ll i, x;
cin >> i >> x;
--i;
if (B[i] > 1 && x == 1) S.erase(i);
B[i] = x;
if (B[i] > 1) S.insert(i);
}
else{
ll l, r;
cin >> l >> r;
--l;
ll v = 0;
for(ll i = l; i < r; ++i){
if (v < 1){
v += A[i];
}
else{
ll ni = *S.lower_bound(i);
if (ni < r){
if (ni > i){ // Bが1,1,...の箇所のAの累積和
v += bit.rangesum(i, ni);
}
v = max(v + A[ni], v * B[ni]); // AかBの大きいほうを採用
i = ni;
}
else{
v += bit.rangesum(i, r);
break;
}
}
}
cout << v << endl;
}
}
}