[luoguP3606] [USACO17JAN]Building a Tall Barn建谷仓（贪心 + 线段树）

传送门

把线段都读进来然后排序，先按右端点为第一关键字从小到大排序，后按左端点为第二关键字从小到大排序。

注意不能先按左端点后按右端点排序，否则会出现大包小的情况，如下：

——————

　　———

　　 —

然后直接线段树搞就行，先求区间最小值，如果大于零就更新统一减1。

——代码

1 #include <cstdio> 2 #include <iostream> 3 #include <algorithm> 4 #define root 1, 1, n 5 #define ls now << 1, l, mid 6 #define rs now << 1 | 1, mid + 1, r 7 8 const int INF = ~(1 << 31), MAXN = 100001; 9 int n, m, ans; 10 int minn[MAXN << 2], add[MAXN << 2]; 11 12 struct node 13 p[MAXN]; 16 17 inline void swap(int &x, int &y) 18 21 22 inline void push_up(int now) 23 26 27 inline void push_down(int now, int len) 28 36 37 inline void build(int now, int l, int r) 38 44 int mid = (l + r) >> 1; 45 build(ls); 46 build(rs); 47 push_up(now); 48 } 49 50 inline bool cmp(node x, node y) 51 54 55 inline int query(int x, int y, int now, int l, int r) 56 64 inline void update(int x, int y, int now, int l, int r) 65 72 if(l > y || r < x) return; 73 push_down(now, r l + 1); 74 int mid = (l + r) >> 1; 75 update(x, y, ls); 76 update(x, y, rs); 77 push_up(now); 78 } 79 80 int main() 81 90 std::sort(p + 1, p + m + 1, cmp); 91 for(i = 1; i <= m; i++) 92 if(query(p[i].a, p[i].b, root) > 0) 93 ans++, update(p[i].a, p[i].b, root); 94 printf("%d", ans); 95 return 0; 96 }
View Code

上一篇：[HDU2136] Largest prime factor（素数筛）

下一篇：[luoguP1186] 玛丽卡（spfa）

---

线段树 贪心