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"; } }