bzoj 3126
题意：给定数轴$[1,n]$，有$m$个区间，每个区间有且只有一个黑点。不被任何区间包含的点也算黑点。求黑点最大个数。
可以差分约束，建立$a(r)-a(l-1)=1,0 \leq a(i)-a(i-1) \leq 1,-1 \geq a(i-1)-a(i) \geq 0$，但是本题卡SPFA
DP做法：
设$dp(i)$为$i$位置，$i$位置必黑的最优方案。
则
$$
dp(i)=\max_{l[i] \leq j \leq r[i]}(dp(j)+1)
$$
对于$j$的取值集合$[l[i], r[i]]$，我们可以预处理出来。
显然对于一个区间$[x, y]$，在$y+1$位置向左最远选点位置是$x$(否则$[x,y]$没黑点)
在$y$位置向左最近选点位置是$x-1$(否则$[x,y]$有多个黑点)
然后$r$没有加入区间时默认$r[i]=i-1$
区间加完后就做个前缀$\max$和后缀$\min$
然后单调队列优化DP即可。
1、单调队列区间的写法
2、$n+1$位置的妙用
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<map>
#include<stack>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db long double
#define fir first
#define sec second
#define mp make_pair
using namespace std;
namespace flyinthesky {
int n, m, ll[200000 + 5], rr[200000 + 5], dp[200000 + 5];
int q[200000 + 5], l, r;
void clean() {
}
int solve() {
clean();
cin >> n >> m;
for (int i = 1; i <= n + 1; ++i) rr[i] = i - 1, ll[i] = 0, dp[i] = -1;
for (int x, y, i = 1; i <= m; ++i) {
scanf("%d%d", &x, &y);
ll[y + 1] = max(ll[y + 1], x);
rr[y] = min(rr[y], x - 1);
}
for (int i = n - 1; i; --i) rr[i] = min(rr[i], rr[i + 1]);
for (int i = 2; i <= n + 1; ++i) ll[i] = max(ll[i], ll[i - 1]);
l = 1, r = 1, q[1] = 0, dp[0] = 0;
int p = 1;
for (int i = 1; i <= n + 1; ++i) {
if (ll[i] > rr[i]) {dp[i] = -1; continue ;}
while (p <= rr[i] && p <= n) {
while (l <= r && dp[p] >= dp[q[l]]) --r;
q[++r] = p, ++p;
}
while (l <= r && q[l] < ll[i]) ++l; // 放后面
if (dp[q[l]] != -1) dp[i] = dp[q[l]] + 1; else dp[i] = -1;
}
if (dp[n + 1] == -1) printf("-1\n");
else printf("%d\n", dp[n + 1] - 1);
return 0;
}
}
int main() {
flyinthesky::solve();
return 0;
}
/*
2 2
1 5
3 8
2 3
1 2
1 1
2 2
2 2
1 2
1 2
*/
