第3回 ドワンゴからの挑戦状 本選 : D - 「ドワンゴからの挑戦状」製作秘話

こちらは自力では求められなさそう。
http://dwacon2017-honsen.contest.atcoder.jp/tasks/dwango2017final_d

問題

ある初期値不明のN要素の数列Aがあったとする。
ここでQ個のクエリを順に与えたとき、その内容と解が(L,R,X,Y)で与えらえる。
すなわちA[L...R]にそれぞれXを加えたのち、A[L...R]の最大値がYであったことを示す。

各クエリの条件を満たす数列Aが存在するか判定し、存在するなら一例を示せ。

解法

最大値を求めるクエリはあっても、最小値を求めるクエリはない。
よって、各クエリにおいては最大値Yを超えない範囲でできるだけAの値は大きくしたい。

そこで、クエリを逆向きに巻き戻し、最大値がYを超えそうな要素があればそれがYに収まるように値を小さくしていくことを考えよう。
これは区間内の最大値と加算量を保持する遅延伝搬SegTreeで解ける。
こうしてAの初期値の候補を求めた後、改めて各クエリを実行し、条件を満たすか判定しよう。

int N,Q;
int L[202020],R[202020],X[202020],Y[202020];
ll V[202020];


template<class V,int NV> class SegTree_2 {
public:
	vector<V> mi,add;
	SegTree_2(){mi.resize(NV*2,1LL<<58); add.resize(NV*2);};
	V getval(int k) {
		int e = k+NV;
		return mi[e]+add[e];
	}
	void prop(int k) {
		mi[2*k]=min(mi[2*k],mi[k]-add[2*k]);
		add[2*k]+=add[k];
		mi[2*k+1]=min(mi[2*k+1],mi[k]-add[2*k+1]);
		add[2*k+1]+=add[k];
		mi[k]=1LL<<58;
		add[k]=0;
	}
	
	void prop() {
		for(int k=1;k<NV;k++) prop(k);
	}
	
	void update(int x,int y, V A, V M,int l=0,int r=NV,int k=1) {
		if(l>=r) return;
		if(x<=l && r<=y) {
			mi[k]=min(mi[k],M-add[k]);
			add[k]+=A;
		}
		else if(l < y && x < r) {
			prop(k);
			update(x,y,A,M,l,(l+r)/2,k*2);
			update(x,y,A,M,(l+r)/2,r,k*2+1);
		}
	}
};
SegTree_2<ll,1<<20> st2;

template<class V,int NV> class RMQ_range {
public:
	vector<V> val, ma;
	RMQ_range(){ val.resize(NV*2,0); ma.resize(NV*2,0); };
	V getval(int x,int y,int l=0,int r=NV,int k=1) {
		if(r<=x || y<=l) return -1LL<<60;
		if(x<=l && r<=y) return ma[k];
		return max(getval(x,y,l,(l+r)/2,k*2),getval(x,y,(l+r)/2,r,k*2+1)) + val[k];
	}
	
	void update(int x,int y, V v,int l=0,int r=NV,int k=1) {
		if(l>=r) return;
		if(x<=l && r<=y) {
			val[k]+=v;
			ma[k]+=v;
		}
		else if(l < y && x < r) {
			update(x,y,v,l,(l+r)/2,k*2);
			update(x,y,v,(l+r)/2,r,k*2+1);
			ma[k]=max(ma[k*2],ma[k*2+1]) + val[k];
		}
	}
};
RMQ_range<ll,1<<20> rmq;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>Q;
	FOR(i,Q) {
		cin>>L[i]>>R[i]>>X[i]>>Y[i];
		L[i]--;
	}
	for(i=Q-1;i>=0;i--) st2.update(L[i],R[i],-X[i],Y[i]);
	
	st2.prop();
	
	FOR(i,N) {
		V[i]=st2.getval(i);
		rmq.update(i,i+1,V[i]);
	}
	FOR(i,Q) {
		rmq.update(L[i],R[i],X[i]);
		if(rmq.getval(L[i],R[i])!=Y[i]) return _P("NG\n");
	}
	
	_P("OK\n");
	FOR(i,N) _P("%lld ",V[i]);
	_P("\n");
	
}

まとめ

巻き戻し系問題はいつもさっくり解けない…。