P3084 [USACO13OPEN]照片Photo
农夫约翰决定给站在一条线上的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.
输入
5 3
1 4
2 5
3 4
输出
1
根本想不到是dp，有且仅有一只牛<=>
- 至少有一只牛
- 最多有一只牛
设dp[i]：点i必须放一只牛时前i个点最多能放多少只奶牛
显然dp[i]=max(dp[j]+1)
所以，如果点i被某个区间[l,r]覆盖了，j属于该区间的话就不能转移，这样该区间就有两只牛了，在所有的包含i的[l,r]区间里，最小的l就是j+1的最大值，即j要不能大于等于l。
j也不能太小，因为j太小的话，j转移给i中间可能有另一个区间，但是该区间没有放牛，所以，找到l最大的不包含i的区间[l,r]，j>=l时，必然满足j转移给i时，中间没有没有放牛的区间。
这些条件可以预处理，输入区间[l,r]，第一点就是把区间[l,r]的值改为小于等于l，
第二点就是把r+1到最后面的值改为大于等于l。
显然可以正着dp搞出来第二个，反着dp出来第一个，不过，反着dp之前要预处理
但是，dp[n]不一定是答案，所以dp的时候dp到n+1，如果有答案，ans=dp[n+1]-1,
如果dp[n+1]没被更新，就是-1
#include<bits/stdc++.h>
using namespace std;
template<class T>inline bool read(T &x){
x=0;register char c=getchar();register bool f=0;
while(!isdigit(c)){if(c==EOF)return false;f^=c=='-',c=getchar();}
while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();
if(f)x=-x;
return true;
}
template<class T>inline void print(T x){
if(x<0)putchar('-'),x=-x;
if(x>9)print(x/10);
putchar('0'+x%10);
}
typedef long long ll;
const ll inf=0x3f3f3f3f,MAXN=2e5+8,mod=998244353;
#define Init(arr,val) memset(arr,val,sizeof(arr))
#define lowbit(x) (x&(-x))
#define mid ((l+r)>>1)
#define lson (i<<1)
#define rson (i<<1|1)
int n,m;
int dp[MAXN],interval_min[MAXN],sufix_max[MAXN];
int main(){
read(n),read(m);
for(int i=0;i<=n+1;++i)interval_min[i]=i;//预处理，区间最小值不可能大于i
int l,r;
while(m--){
read(l),read(r);
interval_min[r]=min(interval_min[r],l);
sufix_max[r+1]=max(sufix_max[r+1],l);
}
for(int i=1;i<=n+1;++i)//n+1，便于找出答案
sufix_max[i]=max(sufix_max[i-1],sufix_max[i]);
for(int i=n;i>=1;--i)
interval_min[i]=min(interval_min[i+1],interval_min[i]);
for(int i=1;i<=n+1;++i){
l=sufix_max[i];//由[l,r)区间内找到最大的一个数，更新i
r=interval_min[i];
while(l<r&&l<i){
dp[i]=max(dp[i],dp[l++]+1);
}
if(dp[i]==0)dp[i]=-1;//如果没能更新成功，置为-1，让他不能更新后面的点
}
if(dp[n+1]>1)dp[n+1]--;
print(dp[n+1]);
return 0;
}
发现，l,r,都是递增的，可以用滑动窗口最值优化。
#include<bits/stdc++.h>
using namespace std;
template<class T>inline bool read(T &x){
x=0;register char c=getchar();register bool f=0;
while(!isdigit(c)){if(c==EOF)return false;f^=c=='-',c=getchar();}
while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();
if(f)x=-x;
return true;
}
template<class T>inline void print(T x){
if(x<0)putchar('-'),x=-x;
if(x>9)print(x/10);
putchar('0'+x%10);
}
typedef long long ll;
const ll inf=0x3f3f3f3f,MAXN=2e5+8,mod=998244353;
#define Init(arr,val) memset(arr,val,sizeof(arr))
#define lowbit(x) (x&(-x))
#define mid ((l+r)>>1)
#define lson (i<<1)
#define rson (i<<1|1)
int n,m;
int dp[MAXN],interval_min[MAXN],sufix_max[MAXN];
struct Node{int val,pos;};
deque<Node>que;
int main(){
read(n),read(m);
for(int i=0;i<=n+1;++i)interval_min[i]=i;
int l,r;
while(m--){
read(l),read(r);
interval_min[r]=min(interval_min[r],l);
sufix_max[r+1]=max(sufix_max[r+1],l);
}
for(int i=1;i<=n+1;++i)
sufix_max[i]=max(sufix_max[i-1],sufix_max[i]);
for(int i=n;i>=1;--i)
interval_min[i]=min(interval_min[i+1],interval_min[i]);
int add=0;//记录当前已经添加到了哪个点
for(int i=1;i<=n+1;++i){
l=sufix_max[i];
r=interval_min[i];
while(!que.empty()&&que.front().pos<l)que.pop_front();
if(l>add)add=l;//说明add到l有一大堆不需要加进去，当然以后更不需要加进去
while(add<r){
if(dp[add]==-1){add++;continue;}//-1不添加
if(!que.empty()&&dp[add]>=que.back().val)que.pop_back();
else {que.push_back((Node){dp[add],add});add++;}
}
if(que.empty())dp[i]=-1;
else dp[i]=que.front().val+1;
}
if(dp[n+1]>1)dp[n+1]--;
print(dp[n+1]);
return 0;
}
deque有些慢，优化后从85ms->100ms
用数组代替后是70ms，数据太水了，O(N^2)都不卡掉，应该是数据区间太小了。