| Time Limit: 1000MS | Memory Limit: 65536K | |
| Total Submissions: 73869 | Accepted: 21303 |
Description
Input
Output
Sample Input
1 5 1 4 2 6 8 10 3 4 7 10
Sample Output
4
这题注意要离散化就OK了 ，线段树离散化 ，
但是要注意一个坑点
if (sum[i] - sum[i - 1] > 1) sum[m++] = sum[i - 1] + 1;
要加一个点，避免区间不正确覆盖。
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 using namespace std; 5 const int maxn = 2e4 + 10; 6 int tree[maxn << 4], a[maxn], b[maxn]; 7 int sum[3 * maxn], vis[3 * maxn], ans; 8 void init() { 9 memset(tree, -1, sizeof(tree)); 10 memset(vis, 0, sizeof(vis)); 11 } 12 void pushdown(int rt) { 13 tree[rt << 1] = tree[rt << 1 | 1] = tree[rt]; 14 tree[rt] = -1; 15 } 16 void updata(int l, int r, int x, int y, int rt, int v) { 17 if (x <= l && r <= y ) { 18 tree[rt] = v; 19 return ; 20 } 21 if (tree[rt] != -1) pushdown(rt); 22 int m = (l + r) >> 1; 23 if (x <= m) updata(l, m, x, y, rt << 1, v); 24 if (y > m ) updata(m + 1, r, x, y, rt << 1 | 1, v); 25 } 26 void query(int l, int r, int rt) { 27 if (tree[rt] != -1 ) { 28 if (!vis[tree[rt]]) { 29 vis[tree[rt]] = 1; 30 ans++; 31 } 32 return ; 33 } 34 if (l == r) return ; 35 int m = (l + r) >> 1; 36 query(l, m, rt << 1); 37 query(m + 1, r, rt << 1 | 1); 38 } 39 int main() { 40 int t, n; 41 scanf("%d", &t); 42 while(t--) { 43 init(); 44 scanf("%d", &n); 45 int tot = 0; 46 for (int i = 0 ; i < n ; i++) { 47 scanf("%d%d", &a[i], &b[i]); 48 sum[tot++] = a[i]; 49 sum[tot++] = b[i]; 50 } 51 sort(sum, sum + tot); 52 int m = unique(sum, sum + tot) - sum; 53 int t = m; 54 for (int i = 1 ; i < t ; i++) { 55 if (sum[i] - sum[i - 1] > 1) sum[m++] = sum[i - 1] + 1; 56 } 57 sort(sum, sum + m); 58 for (int i = 0 ; i < n ; i++) { 59 int x = lower_bound(sum, sum + m, a[i]) - sum; 60 int y = lower_bound(sum, sum + m, b[i]) - sum; 61 updata(0, m - 1, x, y, 1, i); 62 } 63 ans = 0; 64 query(0, m - 1, 1); 65 printf("%d\n", ans); 66 } 67 return 0; 68 }
原文：https://www.cnblogs.com/qldabiaoge/p/9058416.html