Codeforces 526F - Pudding Monsters

Problem Statement:
526F - Pudding Monsters


Solution:
A self note for a tough problem. The problem is equivalent to finding the number of segments in an array A, with a property that the elements in each valid segment is a permutation of a consecutive sequence of numbers. Furthermore, A itself is a permutation of [1..n].

The first way to solve this problem is by considering a divide and conquer strategy: Let A[1..n] be the sequence of numbers. Let S(i..j) be the number of valid segments in A[i..j]. Then we can find S(i..j) by splitting A[i..j] into 2 parts A[i..m] and A[m+1..j] where m is (i+j)/2. By recursion, assume we know how to compute S(i..m) and S(m+1..j). What is left is to compute the number of segments that crosses A[i..m] and A[m+1..j]. Let L denote A[i..m], while R denote A[m+1..j]. For all such valid segments M[u..v], we have:

1. Let the highest element in M be Mmax, while the lowest element in M be Mmin, then Mmax - Mmin = v - u.
2. Mmin and Mmax may either be: (1) both in L (or R), or (2) one in L and the other in R.

To solve the first case where both Mmin and Mmax can be found in one side, WLOG in L, we iterate from i to m : let k = max[i..m] - min[i..m], then we check if max[m+1..i+k] and min[m+1..i+k] is within Mmin and Mmax, also check if (i+k) is in [m+1..j]. Do the same for the case where both are in R.

To solve for the second case, suppose that Mmax is in L, iterate u = m to i: let Lmax = max[u..m], Lmin = max[u..m]. Suppose the valid segment is [u..v], and let Rmax = max[m+1..v], Rmin = min[m+1..v]. Then it must hold that Lmax > Rmax and Rmin < Lmin. Furthermore, we must have Lmax - Rmin = v-u. While iterating from m to i, notice that the valid v can only increase in value. Do the same for the other case.

Each of the cases is solvable in O(N), and Since S(N) = 2*S(N/2) + O(N), we have S(N) = O(N lg N).


Another way to solve this problem is by using a segment tree, for which the implementation is provided here. First of all, consider a prefix A[1...i]. For each suffix A[j..i] of A[1..i], let val[i][j] = max[j..i] - min[j..i] - (i-j). This means that val[i][j] equals to 0 if and only if A[i..j] is a valid segment. We also have val[i][j] = max(max[j..i-1], A[i]) - min(min[j..i-1], A[i]) - ((i-1) -j) - 1, for each j <= i-1. This suggests a relationship between val[i-1][j] and val[i][j]:
1. If A[i] is bigger than max[j..i], then val[i][j] can be derived from val[i-1][j] as follows: val[i][j] = val[i-1][j] - max[j..i-1] + A[i] - 1.
2. If A[i] is smaller than min[j..i], then val[i][j] = val[i-1][j] + min[j..i-1] - A[i] -1.
3. Or it might be both, or none of those.

Observe that if max[j..i] is smaller than A[i], then so are all max[k..i] where k < j (symmetrically for min[j..i]). This suggest that we can update the val[i][k] for all k in [1..j] in one batch, which can be done efficiently using segment tree.

For the configuration of the segment tree, the nodes in the tree maintain two information: the minimum val[i][j] in that subtree, and the number of segments having that value. We store the value j on each leaves of the segment tree. The implementation below is based on the lazy propagation of segment tree.

We also need two monotonic queues, one for maintaining the maximum values and one for minimum values. This is because in each iteration of the algorithm we want to find the values in [1..i] that is smaller than A[i] (and vice versa) from the closest to the furthest from A[i].

(Well I think the divide and conquer idea is simpler.)

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 300005;
int minv[4*N], cnt[4*N], add[4*N];
int loq[N], hiq[N];
int a[N];
int n;

void init(int p, int L, int R){
    cnt[p] = 1;
    minv[p] = L;
    add[p] = 0;
    if(L==R){
        return;
    }
    int M = (L+R)/2;
    init(2*p, L, M);
    init(2*p+1, M+1, R);
}

void upd(int p, int L, int R, int S, int T, int val){
    if(R<S || T<L) return;
    if(S <= L && R <= T) {
        add[p] += val;
        return;
    }
    if(add[p]){
        add[2*p] += add[p];
        add[2*p+1] += add[p];
        add[p] = 0;
    }
    int M = (L+R)/2;
    upd(2*p, L, M, S, T, val);
    upd(2*p+1, M+1, R, S, T, val);
    minv[p] = min(minv[2*p]+add[2*p], minv[2*p+1]+add[2*p+1]);
    cnt[p] = 0;
    if(minv[p] == minv[2*p]+add[2*p]){
        cnt[p] += cnt[2*p];
    }
    if(minv[p] == minv[2*p+1]+add[2*p+1]){
        cnt[p] += cnt[2*p+1];
    }
}

int main(){
    scanf("%d",&n);
    int x,y;
    for(int i=0;i<n;++i){
        scanf("%d%d",&x,&y);
        a[x] = y;
    }
    int lo=0, hi=0;
    long long ans = 0;
    init(1, 1, n);
    for(int i=1;i<=n;++i){
        while(hi>0 && a[i] > a[hiq[hi]]){
            int from = (hi-1 == 0) ? 1 : hiq[hi-1]+1;
            int to = hiq[hi];
            upd(1, 1, n, from, to, -a[hiq[hi]]);
            hi--;
        }
        hiq[++hi]=i;
        while(lo>0 && a[i] < a[loq[lo]]) {
            int from = (lo-1 == 0) ? 1 : loq[lo-1]+1;
            int to = loq[lo];
            upd(1, 1, n, from, to, +a[loq[lo]]);
            lo--;
        }
        loq[++lo]=i;
        upd(1, 1, n, (hi-1 == 0 ? 1 : hiq[hi-1]+1), i, a[i]);
        upd(1, 1, n, (lo-1 == 0 ? 1 : loq[lo-1]+1), i, -a[i]);
        upd(1, 1, n, 1, i-1, -1);
        upd(1, 1, n, i, i, -i);
        if(minv[1] + add[1] == 0) ans += cnt[1];
    }
    cout << ans << endl;
    return 0;
}