https://yahoo-procon2017-qual.contest.atcoder.jp/assignmentshttps://yahoo-procon2017-qual.contest.atcoder.jp/tasks/yahoo_procon2017_qual_d
i日目の最適な売り方をした時の商品の残りをBi個としてグラフを考えます。(D,A)はグラフをD日からAだけ下げて、マイナスの値を0になるように調節するような作業になります。経理質問DはD日まで売った数を単に答えればいいです。
ここで一度0になった日にちはそれ以降0以外の値を取らないことに注目します。
するとD日より後で初めて0を取る日にちをLDとすれば、[D, LD)の区間についてAだけ下げればいいです。
そしてマイナスの値を0に調節するんですが、これは各日にちで1回しかしなくて良いです。なので座標圧縮すればO(QlogQ)で全クエリを捌けます。
よくある1回しか使わないの条件ですね。
int Q; ll K; int N; ll C[MAX_N], D[MAX_N], A[MAX_N]; vector<ll> vec; segtree prod; BIT sale; set<int> zero; void bit_show(BIT& bit) { vector<ll> vec; rep(i, 0, bit.n) vec.pb(bit.get(i, i + 1)); debug(vec); } int cd(ll a) { return lower_bound(all(vec), a) - vec.begin(); } void solve() { cin >> Q >> K; rep(i, 0, Q) { cin >> C[i]; if(C[i] == 1) cin >> D[i] >> A[i]; else cin >> D[i]; vec.pb(D[i]); } sort(all(vec)); vec.erase(unique(all(vec)), vec.end()); N = sz(vec); prod.init(N); sale.init(N + 1); zero.insert(N); rep(i, 0, N) { ll d = vec[i]; prod.update(i, i + 1, d * K); } rep(i, 0, Q) { if(C[i] == 1) { int from = cd(D[i]); int to = *zero.lower_bound(from); prod.update(from, to, -A[i]); sale.update(from, from + 1, A[i]); sale.update(to, to + 1, -A[i]); while(true) { pl p = prod.get(from, to); ll v = p.fst, id = p.sec; int temto = *zero.lower_bound(id); // debug("omo", v, id); // prod.show(); if(v >= 0) break; prod.update(id, temto, -v); sale.update(id, id + 1, v); sale.update(temto, temto + 1, -v); zero.insert(id); } } else { int did = cd(D[i]); cout << sale.get(0, did + 1) << "\n"; } // prod.show(); // bit_show(sale); // debug(vi(all(zero))); } }
Editorialの解法も見とかないと。