题意：有t组测试数据，有n张海报，海报按题目给出的顺序覆盖并给出左右区间，问最后能看到几张海报，不完整也算。
题解：线段树+成段更新+离散化 由于题目区间大小有1e7，直接用线段树去做很可能t了，考虑离散化。
我们发现若区间为【1，5】，中间2、3、4其实是没有用处的，所以对于题目给出的区间，我们提取左右端点放入新的数组中，然后去重，这就是离散化。
但是有一个小问题，对于区间【1，3】【5，7】【2，6】，若按照上述方法去做，答案是2，实际我们知道答案是3，因为上述做法将中间的4给忽略了，这里我们只要对于新的数组中间隔大于1的相邻元素之间再插入一个点即可。
然后就是线段树的成段更新，由于根的左右子树表示的值不同，我们直接将根的值置为0。
#define _CRT_SECURE_NO_WARNINGS #include<iostream> #include<cstdio> #include<string> #include<cstring> #include<algorithm> #include<queue> #include<stack> #include<cmath> #include<vector> #include<fstream> #include<set> #include<map> #include<sstream> #include<iomanip> #define ll long long using namespace std; const int MAXN = 1e5 + 5; ll sum[MAXN << 2], add[MAXN << 2]; bool vis[MAXN]; struct Node { int l, r; int mid() { return (l + r) >> 1; } } tree[MAXN << 2]; void PushDown(int rt, int m) { if (add[rt]) { add[rt << 1] = add[rt]; add[rt << 1 | 1] = add[rt]; sum[rt << 1] = add[rt]; sum[rt << 1 | 1] = add[rt]; add[rt] = 0; //其实这题sum数组没必要，与add等价 } } void build(int l, int r, int rt) { tree[rt].l = l; tree[rt].r = r; add[rt] = 0; if (l == r) { sum[rt] = 0; return; } int m = tree[rt].mid(); build(l, m, rt << 1); build(m + 1, r, rt << 1 | 1); sum[rt] = 0; } void update(int c, int l, int r, int rt) { if (tree[rt].l == l && r == tree[rt].r) { add[rt] = c; sum[rt] = c; return; } if (tree[rt].l == tree[rt].r) return; PushDown(rt, tree[rt].r - tree[rt].l + 1); int m = tree[rt].mid(); if (r <= m) update(c, l, r, rt << 1); else if (l > m) update(c, l, r, rt << 1 | 1); else { update(c, l, m, rt << 1); update(c, m + 1, r, rt << 1 | 1); } sum[rt] = 0; } int query(int l, int r, int rt) { if (sum[rt] && !vis[sum[rt]]) { vis[sum[rt]] = true; return 1; } if (l == r) return 0; PushDown(rt, tree[rt].r - tree[rt].l + 1); int m = tree[rt].mid(); int res = 0; if (r <= m) res += query(l, r, rt << 1); else if (l > m) res += query(l, r, rt << 1 | 1); else { res += query(l, m, rt << 1); res += query(m + 1, r, rt << 1 | 1); } return res; } int t, n, x[100005], y[100005], lisan[200005], l, r; int main() { scanf("%d", &t); while (t--) { memset(vis, false, sizeof(vis)); scanf("%d", &n); int cnt = 0; for (int i = 1; i <= n; i++) { scanf("%d%d", &x[i], &y[i]); lisan[cnt++] = x[i]; lisan[cnt++] = y[i]; } sort(lisan, lisan + cnt); cnt = unique(lisan, lisan + cnt) - lisan; int len = cnt; for (int i = 0; i < cnt - 1; i++) { if (lisan[i + 1] - lisan[i] > 1) lisan[len++] = lisan[i] + 1; } sort(lisan, lisan + len); build(1, len, 1); for (int i = 1; i <= n; i++) { l = lower_bound(lisan, lisan + len, x[i]) - lisan; r = lower_bound(lisan, lisan + len, y[i]) - lisan; update(i, l + 1, r + 1, 1); } printf("%d\n", query(1, len, 1)); } return 0; }