luogu3084 Photo 单调队列优化DP

题目大意

　　农夫约翰决定给站在一条线上的N(1 <= N <= 200,000)头奶牛制作一张全家福照片，N头奶牛编号1到N。于是约翰拍摄了M(1 <= M <= 100,000)张照片，每张照片都覆盖了连续一段奶牛：第i张照片中包含了编号a_i 到 b_i的奶牛。但是这些照片不一定把每一只奶牛都拍了进去。在拍完照片后，约翰发现了一个有趣的事情：每张照片中都有且仅有一只身上带有斑点的奶牛。约翰意识到他的牛群中有一些斑点奶牛，但他从来没有统计过它们的数量。 根据照片，请你帮约翰估算在他的牛群中最多可能有多少只斑点奶牛。如果无解，输出“-1”。

题解

状态的设计

　　我一开始看见了区间，便老是往数据结构那里想，花费了很长时间；后来想到了动规，希望用f(i, j)来表示前i头牛、前j张照片中最多会有多少斑点牛，却发现这样的决策具有后效性。

　　避免后效性的方法便是增加限制条件。我们让f(i)指第i头牛是有斑点的情况下前i头奶牛中最多会有多少斑点牛即可。

状态的转移

　　本题的难点之一在于可以转移的转移的状态范围不固定。i的前一头斑点牛必须在i所在任何区间的左侧，而且它要么被在i所在的左端点最靠左的区间a的相邻左侧的区间b内，要么位于a与b间不被区间包含的部分中。因此，可以转移到i的状态组成了一个区间[_cows[i].PrevL, _cows[i].PrevR]。PrevR便是a的左端点-1，PrevL便是b的左端点。因此递归式为f(i) = max(f[j]+1|j∈[_cows[i].PrevL, _cows[i].PrevR])。由于转移来源是个区间，所以我们可以用单调队列来优化。

PrevL, PrevR的求法

　　这是一个极其新颖的做法：若我们知道一个序列是单调不减的，有很多元素都重复，那么我们可以把序列中值开始变化的分界点的值求出来，然后从前到后或从后往前扫描一遍即可求出这个序列。

　　我们知道随着i的递增, _cows[i].PrevL,PrevR都是递增的。那么分界点在哪里呢？若PrevL变化，则i在一个区间的右端点+1处；若PrevR变化，则i在一个区间的右端点处。由于取min和取max的区别，我们PrevL从左到右扫描，PrevR从右到左扫描。

　　注意我们以上都没有提到“区间的左端点”这个位置，因为区间的左端点可能并不是PrevL的分界点，因为若该区间左侧有一段空白，PrevL不变。另外PrevR的分界点可能会漏掉，因为一段区间右端点以后不一定紧跟另一个区间的左端点。

最后输出的结果

　　错误求法是DP完后，对所有i取最大值。结果是会漏掉-1的情况。原因是F[i]指考虑负责包含[1, i]这些点的区间，以后的区间没有考虑。若最大值是在前面取的，一些右面的区间可就没有对应的点喽！

　　正确的做法是后部增加一个奶牛，求它的F值就对了。这样也可以迅速得知-1的情况。

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

const int MAX_RANGE_CNT = 100010, MAX_ID = 200010, MINF = 0xcfcfcfcf;

int TotId, TotRange;

int F[MAX_ID];

struct Range

{

    int L, R;

    bool operator < (const Range& a) const

    {

        return L < a.L;

    }

}_ranges[MAX_RANGE_CNT];

struct Cow

{

    int PrevL, PrevR;

}_cows[MAX_ID];

struct SlideWindow

{

private:

    struct Queue

    {

    private:

        int A[MAX_ID];

        int Head, Tail;

    public:

        Queue():Head(0), Tail(0){}

        void push_back(int x) { A[Tail++] = x; }

        void pop_back() { Tail--; }

        int back() { return A[Tail - 1]; }

        void pop_front() { Head++; }

        int front() { return A[Head]; }

        bool empty() { return Head == Tail; }

    }IdQ;

    int Tail;

public:

    SlideWindow(): Tail(-1){}

    int Move(int tail, int len)

    {

        while (Tail < tail)

        {

            Tail++;

            int head = Tail - len + 1;

            while (!IdQ.empty() && IdQ.front() < head)

                IdQ.pop_front();

            while (!IdQ.empty() && F[IdQ.back()] < F[Tail])

                IdQ.pop_back();

            IdQ.push_back(Tail);

        }

        if (len <= 0)

            return MINF;

        return F[IdQ.front()];

    }

    int GetMax()

    {

        return F[IdQ.front()];

    }

};

void Read()

{

    scanf("%d%d", &TotId, &TotRange);

    for (int i = 1; i <= TotRange; i++)

        scanf("%d%d", &_ranges[i].L, &_ranges[i].R);

    TotId++;

}

int NoAns;

void SetCoverL()

{

    sort(_ranges + 1, _ranges + TotRange + 1);

    for (int i = 1; i <= TotId; i++)

        _cows[i].PrevR = i - 1;

    for (int i = 1; i <= TotRange; i++)

    {

        _cows[_ranges[i].R].PrevR = min(_cows[_ranges[i].R].PrevR, _ranges[i].L - 1);

        _cows[_ranges[i].R + 1].PrevL = max(_cows[_ranges[i].R + 1].PrevL, _ranges[i].L);

    }

    for (int i = 2; i <= TotId; i++)

        _cows[i].PrevL = max(_cows[i].PrevL, _cows[i - 1].PrevL);

    for (int i = TotId - 1; i >= 1; i--)

        _cows[i].PrevR = min(_cows[i].PrevR, _cows[i + 1].PrevR);

}

int DP()

{

    memset(F, MINF, sizeof(F));

    F[0] = 0;

    static SlideWindow g;

    for (int i = 1; i <= TotId; i++)

    {

        F[i] = g.Move(_cows[i].PrevR, _cows[i].PrevR - _cows[i].PrevL + 1) + 1;

    }

    return F[TotId] < 0 ? -1 : F[TotId] - 1;

}

int main()

{

    Read();

    SetCoverL();

    printf("%d\n", DP());

    return 0;

}