みんなのプロコン予選 : D - 工場

うーん、最近AtCoder系での成績がひどいぞ…。
http://yahoo-procon2017-qual.contest.atcoder.jp/tasks/yahoo_procon2017_qual_d

問題

工場は1日にK個の商品を作るとする。
以下のクエリiに順次答えよ。

• D[i]日目にA[i]個の注文が入った。工場にある商品のうち、(在庫があれば)最大A[i]個まで販売可能である。
• ここまでのクエリで入った注文に対し、D[i]目までの注文に答えて最適に商品を販売する場合、最大何個販売できるか答えよ。

解法

D[i]目までの生産量はD[i]*Kで容易にわかる。
D[i]日目までの注文に際し、在庫がある限りできるだけ多く売るのが最適なのは容易にわかる。
あとはその際D[i]に何個在庫があるかを求められれば、差を取って販売数がわかる。

ここで問題は、在庫がない限り売れないことである。
在庫がマイナスの値を取ることが可能ならば、各日の(生産量-注文数)の総和を取っていけばよい。
ただ、実際は途中在庫がマイナスになることは許されないので、(生産量-注文数)はそれよりも多くなることが考えられる。

d日目の(生産量-注文数)をB[d]とする。
在庫マイナスを無視すれば、日付半開区間[L,R)に突入する直前(L-1)日目終了時の在庫がZ個の場合、R日目開始前の在庫はZ+sum(B[L...R))となる。
しかし途中でマイナスになることを避けるならば、一時的に販売量が落ちるので在庫はZ+sum(B[L...R))より大きくなる。
途中でマイナスになりかねないタイミングが複数あった場合、１回でもマイナスを回避するために販売数を絞ると、あとの商品の増減は固定される。
よってマイナスになるタイミングは区間[L,R)で在庫数が最低になるタイミングの１回だけを考えればよく、その場合R日目開始前の在庫も1通りしかない。
そこで区間C=[L,R)に対しパラメータX[C]、Y[C]を以下のように定める。

• 途中でマイナスを回避するタイミングがある場合、R日目終了後の在庫はY[C]となる。
• そうでない場合、区間開始前から区間終了後まで在庫はX[C]増加する。

上記の値は区間開始時の在庫の量で決まるので、結局区間終了時の在庫数はmax(Y[C],Z+X[C])であらわせる。

あとはこのX[C]、Y[C]をSegTreeの要領で更新・連結していけば、２種類目のクエリに対しY[[0,D[i]+1)]がD[i]日目終了時の在庫数となる。
連続する２つの区間C=[P,Q)とC'=[Q,R)を連結した区間C''=[P,R)を考えるとき、X,Yの値は以下のようになる。
区間C終了時の在庫はmax(Y[C],Z+X[C])なので、区間C'終了時の在庫を考えるとmax(Y[C'],max(Y[C],Z+X[C])+X[C'])=max(max(Y[C'],Y[C]+X[C']),Z+X[C]+X[C'])。
よってX[C'']=X[C]+X[C']、Y[C'']=max(Y[C'],Y[C]+X[C'])となる。

int Q;
ll K;
int T[101010],D[101010],A[101010];
vector<ll> V;

template<class V,int NV> class SegTree_1 {
public:
	vector<V> X,Y;
	
	SegTree_1(){
		X=vector<V>(NV*2);
		Y=vector<V>(NV*2);
	}
	pair<ll,ll> getval(int x,int y,int l=0,int r=NV,int k=1) { // x<=i<y
		if(r<=x || y<=l) return {0,0};
		if(x<=l && r<=y) return {X[k],Y[k]};
		auto A=getval(x,y,l,(l+r)/2,k*2);
		auto B=getval(x,y,(l+r)/2,r,k*2+1);
		return {A.first+B.first,max(B.first+A.second,B.second)};
	}
	void diff(int entry, V v) {
		entry += NV;
		X[entry]+=v;
		while(entry>1) {
			entry>>=1;
			X[entry]=X[entry*2]+X[entry*2+1];
			Y[entry]=max(X[entry*2+1]+Y[entry*2],Y[entry*2+1]);
		}
	}
};

SegTree_1<ll,1<<20> st;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>Q>>K;
	V.push_back(0);
	FOR(i,Q) {
		cin>>T[i];
		if(T[i]==1) {
			cin>>D[i]>>A[i];
		}
		else {
			cin>>D[i];
		}
		V.push_back(D[i]);
	}
	
	sort(ALL(V));
	V.erase(unique(ALL(V)),V.end());
	for(i=1;i<V.size();i++) {
		st.X[i+(1<<20)] += 1LL*K*(V[i]-V[i-1]);
	}
	for(i=(1<<20)-1;i>=1;i--) {
		st.X[i] = st.X[2*i]+st.X[2*i+1];
		st.Y[i] = max(st.X[2*i+1]+st.Y[2*i],st.Y[2*i+1]);
	}
	
	FOR(i,Q) {
		x = lower_bound(ALL(V),D[i])-V.begin();
		if(T[i]==1) {
			st.diff(x,-A[i]);
		}
		else {
			ll tot=1LL*K*D[i];
			auto ret=st.getval(0,x+1);
			cout<<tot-ret.second<<endl;
		}
	}
	
	
}

まとめ

セグメントを連結していくところまでは思いつけたのに、連結する際に取った状態変数がいまいちで、連結処理がうまく書けなかった。
せっかく似たテクをCodeforcesで覚えたのになぁ…。