背景
在线段树的通常用法中，线段树的节点是有2种不同的意义的，
一种是离散型的：一个节点虽然描述的是一个区间[3, 9]，但是实际上这样一个区间是{3, 4, 5, 6, 7, 8, 9}这样的意义。
而另一种就是连续型的：一个节点如果描述的是一个区间[3, 9]，它就确确实实描述的是在数轴上从3这个标记到9这个标记的这一段。
这两种不同的意义有什么区别呢？
有这样的几个区别：
1.叶子节点：在离散型中，叶子节点是[i, i]，而连续性中是[i, i + 1]；
2.分解区间：在离散型中，一段区间是分解成为[l, m], [m + 1, r]，而在连续型中，是分解成为[l, m], [m, r]；3.其他所有类似的判定问题。
题目
小Hi和小Ho在回国之后，重新过起了朝7晚5的学生生活，当然了，他们还是在一直学习着各种算法~
这天小Hi和小Ho所在的学校举办社团文化节，各大社团都在宣传栏上贴起了海报，但是贴来贴去，有些海报就会被其他社团的海报所遮挡住。看到这个场景，小Hi便产生了这样的一个疑问——最后到底能有几张海报还能被看见呢？
于是小Ho肩负起了解决这个问题的责任：因为宣传栏和海报的高度都是一样的，所以宣传栏可以被视作长度为L的一段区间，且有N张海报按照顺序依次贴在了宣传栏上，其中第i张海报贴住的范围可以用一段区间[a_i, b_i]表示，其中a_i, b_i均为属于[0, L]的整数，而一张海报能被看到当且仅当存在长度大于0的一部分没有被后来贴的海报所遮挡住。那么问题就来了：究竟有几张海报能被看到呢？
输入
每个测试点（输入文件）有且仅有一组测试数据。
每组测试数据的第1行为两个整数N和L，分别表示总共贴上的海报数量和宣传栏的宽度。
每组测试数据的第2-N+1行，按照贴上去的先后顺序，每行描述一张海报，其中第i+1行为两个整数a_i, b_i，表示第i张海报所贴的区间为[a_i, b_i]。
对于100%的数据，满足N<=10^5，L<=10^9，0<=a_i<b_i<=L。
输出
对于每组测试数据，输出一个整数Ans，表示总共有多少张海报能被看到。
5 10 4 10 0 2 1 6 5 9 3 4
5
解法
区间离散化+连续型线段树
代码
#include <iostream>
#include <string.h>
#include <map>
#include <set>
#include <vector>
using namespace std;
int tree[1000000];
void down(int l, int r, int idx){
if(tree[idx] && l<r){
tree[idx*2+1] = tree[idx*2+2] = tree[idx];
tree[idx] = 0;//@error: lost this
}
}
void _set(int l, int r, int idx, int a, int b, int d){
if(a<=l && b>=r) { tree[idx] = d; return; }
int mid = (l+r)/2;
down(l, r, idx);
if(a>=mid) _set(mid, r, idx*2+2, a, b, d);
else if(b<=mid) _set(l, mid, idx*2+1, a, b, d);
else{
_set(mid, r, idx*2+2, mid, b, d); // b > mid
_set(l, mid, idx*2+1, a, mid, d); // a < mid
}
}
int get(int l, int r, int idx, int a){
while(!tree[idx] && l+1<r){
int mid = (l+r)/2;
if(a>=mid) l = mid , idx = idx*2 + 2;
else r = mid, idx = idx*2 + 1;// a + 1 <= mid
}
return tree[idx];
}
int main(){
int n, l; cin>>n>>l;
memset(tree, 0, sizeof(tree));
set<int> ss; vector<pair<int, int> > pp;
for(int i=1; i<=n; i++){
int a, b; cin>>a>>b;
ss.insert(a); ss.insert(b);
pp.push_back(pair<int, int>(a, b));
}
map<int, int> mm; int i = 0;
for(set<int>::iterator it = ss.begin(); it!= ss.end(); it++){
mm[*it] = i++;
}
int N = ss.size();
for(int i=1; i<=n; i++){
pair<int, int> &p = pp[i-1];
_set(0, N-1, 0, mm[p.first], mm[p.second], i);
}
set<int> res;
for(int i=0; i < N - 1; i++){//@attention: i<N-1, the last point
int j = get(0, N-1, 0, i); // [i, i+1]
if(j) res.insert(j);
}
cout<<res.size()<<endl;
return 0;
}