//这道 题似乎是默认一定会成功的,而且是按大小顺序输入的?
#include "stdafx.h" #include <cstdio> #include <cstdlib> #define MAXN 100001 #define MAX 500001 struct node { long x, y, w; } T[MAXN * 2]; long N, M, S, Val; void build(long p, long a, long b)//建树 { T[p].x = a; T[p].y = b; T[p].w = MAX;//为最大值是因为如果不是从头开始覆盖 的,那么是无效的,只能是最大值 if (a + 1 < b) { build(p * 2, a, a + b >> 1); build(p * 2 + 1, a + b >> 1, b); } } void update(long p)//维护所有包含点s的结点 { if (T[p].w > Val) T[p].w = Val; if (T[p].x + 1 < T[p].y) if (S <= T[p].x + T[p].y >> 1)//更新左边 update(p * 2); else update(p * 2 + 1); } long query(long p, long a, long b)//找到 s 之前较小的标志//因为要顺序输入才有效,因此要加上s之前较小的覆盖线段数 { if ((a <= T[p].x) && (T[p].y <= b))//如果 包含 则返回 return T[p].w; long mid = T[p].x + T[p].y >> 1; if (b <= mid)// 左子树 return query(p * 2, a, b); if (mid <= a)//右子树 return query(p * 2 + 1, a, b); //左右子树都有包含的时候 long t1 = query(p * 2, a, mid); long t2 = query(p * 2 + 1, mid, b); return t1 < t2 ? t1 : t2; } int main() { long temp; while (scanf_s("%ld%ld", &N, &M) != EOF) { build(1, 0, N);//0 到 40建树 ,1为 初始下标 S = 1;//S表示更新范围 Val = 0; update(1);//维护所有包含点s的结点 将开头的线段的 覆盖数初始为0,但下一个输入线段覆盖了它,才是有效的 while (M--) { scanf_s("%ld%ld", &temp, &S); Val = query(1, temp - 1, S - 1) + 1;//temp-1是因为题是从0开始建树的,s-1是因为搜索s的前一个线段的标志是为多少 update(1);//从下标1的地方 开始更新 } printf("%ld\n", query(1, N - 1, N)); } return 0; }
好吧,我只是勤劳的搬运工,谁叫自己上课不好好听的。。。。理解也理解了很久呀!!!!