TopCoder SRM 786 : Div2 Hard SuffixDecomposition

これはDiv2 Hardにしても簡単。
https://community.topcoder.com/stat?c=problem_statement&pm=16132&rd=17989

問題

数列AがBより小さいとは、Aの最大値がBの最小値より小さいものと定義する。
f(C) := 数列CをC1+C2+C3,,,と分割したとき、C1＜C2＜C3....が保てるような分割数の最大値
とする。

ここで整数列Sが与えられる。
Sの各suffix S'において、f(S')の総和を求めよ。

解法

まずf(C)の求め方を考える。
Cの要素を後ろから順に、処理済みの数列群に追加していくことを考える。
今、途中まで処理を行ったところC1+C2+C3と分割されており、ここの先頭にvを加える。

• v＜C1なら、C0={v}としてC0+C1+C2+C3となる。
• v≧C1なら、C1'={v}+C1としてC1'+C2+C3となる。
  • その際、C1'＜C2かわからないので、max(C1')とmin(C2)を比較し、max(C1')≧min(C2)なら連結してC2'=C1'+C2とする。
  • 同様に順次数列を連結する

あとはこれを愚直に実装すればよい。
以下のコードでは、分割した個々の数列は最小値と最大値だけ持つようにし、そのスタックを伸び縮みして処理させている。

class SuffixDecomposition {
	public:
	long long findTotalFun(vector <int> P, int A0, int X, int Y, int B0, int X1, int Y1, int N) {
		vector<ll> A,B,S;
		A.push_back(A0);
		B.push_back(B0);
		while(A.size()<N) {
			A.push_back((A.back()*X+Y)%1812447359);
			B.push_back((B.back()*X1+Y1)%1812447359);
		}
		FORR(p,P) S.push_back(p);
		while(S.size()<N) S.push_back(max(A[S.size()],B[S.size()]));
		reverse(ALL(S));
		ll ret=0;
		vector<pair<ll,ll>> C;
		C.push_back({1LL<<40,1LL<<40});
		FORR(s,S) {
			ll L=s,R=s;
			while(C.back().first<=R) {
				L=min(L,C.back().first);
				R=max(R,C.back().second);
				C.pop_back();
			}
			C.push_back({L,R});
			
			ret+=C.size()-1;
		}
		return ret;
	}
}

まとめ

900ptでもいいね。