刚接触离散化，开始对其百思不得其解，现在回想，顿时开窍，对线段树的离散化才有了初步了解。于是打算写上这么一篇博文，分享自己的理解过程。注：文中的代码并非完全由我原创，是我根据自己的理解对其进行了些修改，如有错误，望指正。
题目链接：点击打开链接
题目大意： 在一面墙上以一定的先后顺序贴上海报，每张海报有对应的起始及终止区间，求当最后一张海报贴完后，墙上没有被完全遮盖的海报张数。 题目分析： 个人觉得这个题目比较经典，因为它不但包括了线段树的基本框架，还融入了延迟更新与离散化，考察方面较广。 我们知道线段树在解决区间问题上是比较适用的，而这题的每张海报其实就是一个区间，所以此题用线段树求解是比较方便的。然而这个题的特殊之处是它数据范围（海报的左右端点1<=li<=ri<=10^7）所以直接开一个这么大的线段树数组不但很可能会超内存，在查询时还一定会超时。所以这里需要运用到离散化的思想，将每个端点的值分别数1-n建立映射关系，以适当减小两端点的间隔差。 但是进行普通的映射是存在问题的。如：当三张海报的区间分别是[1-10],[1-4],[7-10]时，在对其端点进行排序后，若建立的映射为： y: 1 4 7 10 x: 1 2 3 4 则当输入[1-10]时线段树中对应的区间[1-4]被标记为0（即它是数组中的第一个数据）；输入区间[1-4]时，对应的区间[1-2]被标记为1；输入区间[7-10]时，对应的区间[3-4]。这样一来根据映射，区间[1-10]就被[1-4]和[7-10]所覆盖，而实际上并没有。 为什么会这样呢？其实，是在进行上述映射时，原来数据（即海报）的区间间隔差被过度减小了。所以为了不改变原有数据间隔的相对性质，我们在间隔差大于1的两相邻数据间再添加一个数（这个数不对应任何数据，只起到分离两相邻区间的作用），则原来的映射关系就变为： y: 1 4 7 10 x: 1 2 3 4 5 6 7
我们这样做其实是将原来两相邻区间间隔差大于2的缩小至2，而非为1。如原来[1-4],[7-10],对应的区间[1-2],[2-3]的间隔差为3-2=1，而修改后的为5-3=2。
下面是代码：
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int maxn = 10010; #define lson l, mid, rt<<1 #define rson mid+1, r, rt<<1|1 bool judge[maxn]; struct Post { int li; int ri; }post[maxn]; int Mp[maxn<<3]; //开辟用于映射的数组 int tree[maxn<<4]; int cnt; void pushdown(int rt) { if(tree[rt]!=-1) { tree[rt<<1] = tree[rt]; tree[rt<<1|1] = tree[rt]; tree[rt] = -1; } } void updata(int L, int R, int val, int l, int r, int rt) { if(L<=l && r<=R) { tree[rt] = val; return ; } pushdown(rt); int mid = (l+r)>>1; if(L<=mid) updata(L, R, val, lson); if(R>mid) updata(L, R, val, rson); } void query(int l, int r, int rt) { if(tree[rt]!=-1) { if(!judge[tree[rt]]) cnt++; judge[tree[rt]] = true; return; } if(l == r) //考虑到li == ri情况 return ; int mid = (l+r)>>1; query(lson); query(rson); } //将映射中每张海报的区间端点与海报张贴的顺序匹配 int find(int val, int n) { int l = 0; int r = n; while(l<=r) { int mid = (l+r)>>1; if(Mp[mid]==val) return mid; if(Mp[mid]>val) r = mid-1; else l = mid+1; } return -1; } //建立映射关系 int Mapping(int nn) { sort(Mp, Mp+nn); int m=1, i; for(i=1; i<nn; i++) { if(Mp[i]!=Mp[i-1]) Mp[m++] = Mp[i]; } for(i = m-1; i>0; i--) { if(Mp[i]>Mp[i-1]+1) Mp[m++] = Mp[i-1] +1; } sort(Mp, Mp+m); return m; } int main() { int c, n; scanf("%d", &c); while(c--) { scanf("%d", &n); int i, nn=0; for(i=0; i<n; i++) { scanf("%d%d", &post[i].li, &post[i].ri); Mp[nn++]= post[i].li; Mp[nn++]=post[i].ri; } int m = Mapping(nn); memset(tree, -1, sizeof(tree)); for(i=0; i<n; i++) { int l = find(post[i].li, m-1); int r = find(post[i].ri, m-1); updata(l, r, i, 0, m-1, 1); } memset(judge, false, sizeof(judge)); cnt = 0; query(0, m-1, 1); printf("%d\n", cnt); } return 0; }