题意
是人都读得懂,我不是人。
解法
线段树/贪心都有人写了,那我就来个斯特表优化 DP
吧。
转移就是 $dp_{r_i} = \min_{l_i - 1 \leq i < r_i} dp_i + 1$。
众所周知,斯特表可以在末尾添加元素,时间为 $\log$ 级,我们发现这个题目的转移似乎就只有在末尾添加,然后挑一个区间查询最值,正好可以运用上斯特表,需要注意的细节有当两个区间的右端点重合时,按左端点排序,然后插入到斯特表时判断这个区间的右端点是否之前有过,没有再插入到斯特表中。
代码
#include <iostream>
#include <algorithm>
#include <climits>
using namespace std;
const int N = 1e6 + 5, Log = 20, Max = INT_MAX >> 1;
struct Seg {
int l, r;
} s[N];
int n, m, t, f[Log + 1][N];
bool cmp( Seg &i, Seg &j ) {
return i.r ^ j.r ? i.r < j.r : i.l < j.l;
}
void update_back( int v ) {
f[0][m] = v;
for (int i = 1; m - (1 << i) + 1 >= 0; ++i) {
f[i][m] = min({f[i][m], f[i - 1][m], f[i - 1][m - (1 << i - 1)]});
}
++m;
}
int query( int l, int r ) {
int res = Max;
for (int i = Log - 1, le = r - l + 1; ~i; --i) {
if (le >> i & 1) {
res = min(res, f[i][l + (1 << i) - 1]);
l += 1 << i;
}
}
return res;
}
int main() {
ios :: sync_with_stdio(0), cin.tie(0);
cin >> n >> t;
fill (f[0] + 0, f[Log] + N, Max);
for (int i = 1; i <= n; ++i) {
cin >> s[i].l >> s[i].r;
}
sort (s + 1, s + n + 1, cmp);
int lst = 1;
update_back(0);
for (int i = 1; i <= n; ++i) {
for (int j = lst; j < s[i].r; ++j) {
update_back(Max);
}
lst = s[i].r + 1;
if (s[i].r ^ s[i - 1].r) {
update_back(query(s[i].l - 1, s[i].r - 1) + 1);
}
}
return cout << (query(t, t) ^ Max ? query(t, t) : -1), 0;
}