Google Code Jam 2019 Round 3 : B. Pancake Pyramid

これはCodeforcesチックだし、もうちょい粘って考えればよかった…。
https://codingcompetitions.withgoogle.com/codejam/round/0000000000051707/00000000001591be

問題

長さNの整数列Aが与えられる。
全ての部分列A[L,R]に対し、以下の総和をmod 10^9+7で求めよ。

• 数列がピラミッド状になる、すなわち頭から途中まで単調増加で、その後単調減少になるよう、任意の要素に任意の正整数を加算する。
• 異なる部分列を考えるときには、加算量はそれぞれ変えてよい。

解法

まず数列に対し加算量が最小となるケースを考えよう。
これは数列中最大要素が単調増加と単調減少の境になるようにすればよい。

これを踏まえ、以下を考えていく。
X[L,R] := A[L,R]が単調増加となるように必要な加算量の総和
Y[L,R] := A[L,R]が単調減少となるように必要な加算量の総和

部分列A[L,R]の最大要素がMである場合、A[L,R]における加算量はX[L,M]+Y[M+R]となる。
これを踏まえ、A[M]の小さい順に処理していこう。

今Mを処理するとき、A[L...M]≦A[M]である最小のLとA[M]＞A[M...R]である最大のRを考える。
A[L...R]の部分列のうちA[M]を含むものはA[M]が最大値となるので、
X[L..M-1]、X[L+1..M-1]、...、X[M-1,M-1]は右端の数(R-M+1)だけ解に加算されるし、Y[M+1..R]、Y[M+1..(R-1)]、...、Y[M+1,M+1]は左端の数(M-L+1)だけ加算される。
このXとYの加算が手間なので、X,Yを個別に数えるのではなく以下を考えよう。
X'[L,R] = X[L,R] + X[L+1,R] + .... + X[R,R]
Y'[L,R] = Y[L,R] + Y[L,R-1] + .... + Y[L,L]
すると解に加算されるのは X'[L,M-1]*(R-M+1)+Y'[M+1,R]*(M-L+1)となる。

次に、X'[L,M-1]、X'[M+1,R]、Y'[L,M-1]、Y'[M+1,R]あたりからX'[L,R]とY'[L,R]を求めよう。
A[M]はA[L...M]の中で最大なので、X[x,M]=X[x,M-1]なのでX'[L,M]=X'[L,M-1]となる。
xがM以下の時、X[x,R]を考えると、A[M+1]～A[R]はA[M]と同じ値になるように加算しないといけないことを考えると、
X'[L,R]=X'[L,M-1]+X'[M+1,R] + A[M]*(R-M)-(A[M+1]+A[M+2]...+A[R])となる。(Editorialは最後マイナスとなるところが乗算になっていて誤っている)
Y'も同様に更新していこう。

int S;
ll P[1010101];
ll PS[1010101];

ll mo=1000000007;
int L[1010101];
int R[1010101];
ll X[1010101];
ll Y[1010101];





void solve(int _loop) {
	int f,i,j,k,l,x,y;
	
	cin>>S;
	vector<pair<ll,int>> cand;
	set<int> valid;
	FOR(i,S) {
		cin>>P[i];
		L[i]=R[i]=i;
		X[i]=Y[i]=0;
		PS[i+1]=(PS[i]+P[i])%mo;
		cand.push_back({P[i],i});
		valid.insert(i);
	}
	sort(ALL(cand));
	ll ret=0;
	FORR(c,cand) {
		int cur=c.second;
		auto it=valid.find(cur);
		int CL=cur,CR=cur;
		if(it!=valid.begin()) {
			it--;
			if(P[*it]<=P[cur]) CL=*it;
			it++;
		}
		it++;
		if(it!=valid.end()) {
			if(P[*it]<P[cur]) CR=*it;
		}
		
		
		ll LX=X[CL];
		ll RY=Y[CR];
		X[cur]=X[CL]+X[CR];
		Y[cur]=Y[CL]+Y[CR];
		valid.erase(CL);
		valid.erase(CR);
		valid.insert(cur);
		
		CL=L[cur]=L[CL];
		CR=R[cur]=R[CR];
		
		(ret+=(CR-cur+1)*LX)%=mo;
		Y[cur]+=(CR-cur+1)*(P[cur]*(cur-CL)%mo-(PS[cur]-PS[CL]));
		(ret+=(cur-CL+1)*RY)%=mo;
		X[cur]+=(cur-CL+1)*(P[cur]*(CR-cur)%mo-(PS[CR+1]-PS[cur+1]));
		
		X[cur]=(X[cur]%mo+mo)%mo;
		Y[cur]=(Y[cur]%mo+mo)%mo;
	}
	
	_P("Case #%d: %lld\n",_loop,ret);
	
	
}

まとめ

「小さい順にやっていくとO(N^2)かかりそうだな…」と思ってしまった。なんとももったいない…。