题目描述

农夫约翰决定给站在一条线上的N(1 <= N <= 200,000)头奶牛制作一张全家福照片，N头奶牛编号1到N。

于是约翰拍摄了M(1 <= M <= 100,000)张照片，每张照片都覆盖了连续一段奶牛：第i张照片中包含了编号a_i 到 b_i的奶牛。但是这些照片不一定把每一只奶牛都拍了进去。

在拍完照片后，约翰发现了一个有趣的事情：每张照片中都有一只身上带有斑点的奶牛。约翰意识到他的牛群中有一些斑点奶牛，但他从来没有统计过它们的数量。 根据照片，请你帮约翰估算在他的牛群中最多可能有多少只斑点奶牛。如果无解，输出“-1”。

Input

输入输出格式

输入格式：

 

* Line 1: Two integers N and M.

* Lines 2..M+1: Line i+1 contains a_i and b_i.

 

输出格式：

 

* Line 1: The maximum possible number of spotted cows on FJ's farm, or -1 if there is no possible solution.

 

输入输出样例

输入样例#1： 

5 3 1 4 2 5 3 4

输出样例#1： 

1

 

 

其他情况均有解

#include
       
        using namespace std;#define maxn 200005typedef long long ll;#define inf 0x3fffffffstruct node{    int l,r;} a[maxn];int n,m;int rp[maxn],lp[maxn];int q[maxn*2],dp[maxn];int main(){//    freopen("test.txt","r",stdin);    cin>>n>>m;    for(int i=1; i<=n+1; i++)        rp[i]=i-1;    for(int i=1; i<=m; i++)    {        cin>>a[i].l>>a[i].r;        lp[a[i].r+1]=max(lp[a[i].r+1],a[i].l);        rp[a[i].r]=min(rp[a[i].r],a[i].l-1);    }    for(int i=n; i>=1; i--)        rp[i]=min(rp[i],rp[i+1]);    for(int i=2; i<=n+1; i++)        lp[i]=max(lp[i],lp[i-1]);    int head=1;    int tail=1;    int j=1;    for(int i=1; i<=n+1; i++)    {        while(j<=rp[i]&&j<=n)        {            if(dp[j]==-1)            {                j++;                continue;            }            while(dp[j]>dp[q[tail]]&&tail>=head)                tail--;            q[++tail]=j;            j++;        }        while(q[head]
        
         <=tail)            head++;        if(head<=tail)            dp[i]=dp[q[head]]+(i!=n+1?1:0);        else dp[i]=-1;    }    if(dp[n+1]!=-1)        cout<