题意：
有n个数，m个排序器，每个排序器可以把区间ai到bi的数从小到大排序。这m个排序器的输出就是m个排序之后的第n个数。
现在发现有些排序器是多余的。问至少需要多少个排序器可以使得输出不变。排序器的顺序不可以改变。
思路：
这题并没有说这些排序器可以覆盖1到n的所有区间。。。
假设可以，那么就是求最少的区间可以覆盖1到n。
用dp[i]表示覆盖第i个数需要的最少区间数，dp[i] = min(dp[i],dp[s] + 1) ai <= s <= b[i]。
如果单纯的枚举ai到bi，那么时间复杂度为n*m，肯定会t。
找一个区间的最小值，可以想到线段树，所以就用线段树来优化dp，单点查询，单点更新。
注意dp[1] = 0,并且也要在线段树中进行更新。
代码：
#include <stdio.h> #include <string.h> #include <algorithm> using namespace std; const int N = 5e4 + 10; const int inf = 0x3f3f3f3f; int a[N<<2]; int modi[N<<2]; int dp[N]; void pushup(int rt) { a[rt] = min(a[rt<<1],a[rt<<1|1]); } void build(int rt,int l,int r) { if (l == r) { a[rt] = inf; return; } int mid = (l + r) >> 1; build(rt << 1,l,mid); build(rt << 1|1,mid + 1,r); pushup(rt); } int query(int rt,int l,int r,int L,int R) { if (l >= L && r <= R) { return a[rt]; } int mid = (l + r) >> 1; int r1 = inf,r2 = inf; if (L <= mid) r1 = query(rt << 1,l,mid,L,R); if (R > mid) r2 = query(rt << 1|1,mid + 1,r,L,R); return min(r1,r2); } void update(int rt,int l,int r,int p,int v) { if (l == r) { a[rt] = v; return; } int mid = (l + r) >> 1; if (p <= mid) update(rt << 1,l,mid,p,v); else update(rt << 1|1,mid + 1,r,p,v); pushup(rt); } int main() { int t; scanf("%d",&t); while (t--) { int n,m; memset(dp,inf,sizeof(dp)); memset(modi,-1,sizeof(modi)); scanf("%d%d",&n,&m); build(1,1,n); dp[1] = 0; update(1,1,n,1,dp[1]); for (int i = 0;i < m;i++) { int l,r; scanf("%d%d",&l,&r); int k = query(1,1,n,l,r); dp[r] = min(dp[r],k+1); update(1,1,n,r,dp[r]); } printf("%d ",dp[n]); if (t) puts(""); } return 0; } /* 1 40 6 20 30 1 10 10 20 20 30 15 25 30 40 */