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
", DP());
    return 0;
}