Analysis: Optimal Milking by Bruce Merry

Usually the first step in solving incremental-update problems is to solve the problem without the incremental updates, but in this case it can lead one up a blind alley. There is a quite simple DP solution to the non-incremental version of this problem, but it is not at all obvious how to incrementally update this in less than linear time.

Instead, we can find a divide-and-conquer DP solution that will be easier to update. Divide the range in half, and in each half solve the problem again. In fact, we solve four variants of the problem, depending on whether the left and/or right endpoint is allowed to be used. Given these results from the two halves, we can easily combine them to form the results for the whole range. The ranges form a segment tree over the barn, where each tree node depends on its two children, and the answer is held at the root of the tree.

Given this tree structure, it is now clear how we can make incremental updates in O(log N) time: an update affects a leaf of the tree, which in turn requires its O(log N) ancestors to be updated.

Code for the solution appears below, courtesy of Qingqi (Jimmy) Zeng.

#include<iostream>
#include<cstdio>
#include<algorithm>

using namespace std;

int n, d, a, b;
int bb[1<<17], bp[1<<17], pb[1<<17], pp[1<<17], SIZE=(1<<16);

void update(int node) {
    int l=node*2, r=node*2+1;
    pp[node] = max(pb[l]+pp[r], pp[l]+bp[r]);
    pb[node] = max(pb[l]+pb[r], pp[l]+bb[r]);
    bp[node] = max(bb[l]+pp[r], bp[l]+bp[r]);
    bb[node] = max(bb[l]+pb[r], bp[l]+bb[r]);
}

main() {
    freopen("optmilk.in", "r", stdin);
    freopen("optmilk.out", "w", stdout);
    scanf("%d %d", &n, &d);
    for(int i=0;i<n;i++) scanf("%d\n", &bb[SIZE+i]);
    for(int i=SIZE-1;i>0;i--) update(i);
    long long ans=0;
    for(int i=0;i<d;i++) {
	scanf("%d %d", &a, &b); a--;
	bb[SIZE+a] = b;
	for(int j=(SIZE+a)/2;j>0;j/=2) update(j);
	ans += bb[1];
   }
   printf("%lld\n", ans);
}