「みんなのプロコン」D: 工場

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の解法も見とかないと。