CODE FESTIVAL 2016 Final,H: Tokaido

https://cf16-final-open.contest.atcoder.jp/tasks/codefestival_2016_final_h

面白いです。良問。

まずM=1の時を考えて普通にdpすると、
f(j)=max(Ai-sum(j,i)-f(i+1)|i>=j)となります。ただしsum(j,i)=Σ(k=j...i-1)Akです。

よくある添字を1つ減らすテクニックで変形すると
f(j)=max(Aj-f(j+1), max(Ai-sum(j+1,i)-f(i+1)|i>=j+1)-Aj)
=max(Aj-f(j+1),f(j+1)-Aj)=|Aj-f(j+1)|となります。後はfをO(N)で求めればいいです。

満点解法ですが、f(x)=|x-a|のような関数を複数合成した関数f^nについてf^n(x)の値がわかればいいです。
Siをf^n(x)=iを満たすようなxの集合と定義します。
たとえば、S={{0},{1},{2},{3},{4},{5}...}にf(x)=|x-2|を作用させると、
S={{2},{1,3},{0,4},{5}...}のようになります。0と4,1と3がマージされたのがわかると思います。
このように|x-a|を作用させるということはマージをa回行うということになっているので、unionfindを使えばO(Tα(T))(T=ΣAi)でf^n(x)の値を求められます。

あとはクエリに適当に答えるだけです。

int N, Q;
int A[MAX_N];
int ans[MAX_N];
int parval[MAX_N];

UF uf;

void solve() {
	cin >> N;
	rep(i, 0, N - 1) cin >> A[i];
	uf.init(2000000 + 1);

	int prev = 0;
	rer(i, N - 1, 2) {
		int nv = A[i];
		for(int j = 1; j <= nv; j++) {
			uf.unite(prev + nv - j, prev + nv + j);
		}
		prev += nv;
	}
	rep(i, 0, 1000000 + 1) {
		parval[uf.find(prev + i)] = i;
	}
	rep(i, 0, prev + 1) {
		ans[i] = parval[uf.find(i)];
	}
	cin >> Q;
	while(Q--) {
		int x; cin >> x;
		if(prev <= x) cout << A[0] - A[1] + x - prev << "\n";
		else cout << A[0] - A[1] + ans[x] << "\n";
	}
}