http://poj.org/problem?id=2528
https://www.luogu.org/problem/UVA10587
1 5 1 4 2 6 8 10 3 4 7 10
4
题目大意：
给你一个无限长的板子，n（n<=10000)个人依次贴n张等高的海报,给出每张海报所贴的范围li，ri（1<=li<=ri<=10000000)，求出最后还能看见多少张海报。
题解：
一看线段树没跑了对吧？ 就像染色一样，贴一张海报就把那一段染上新颜色， 这就是个很明显的区间修改嘛， 最后统计线段上有多少种不同颜色输出答案就OK了。
但是要注意线段树区间更新问题，给的长度的可能非常大，有1e9，不加处理直接维护一个线段树肯定会MLE,TLE,
但是我们注意到一共最多只有2e4个点，因此我们可以用离散化的思想先对区间进行预处理，所谓的离散化，
在我理解看来就是将一个很大的区间映射为一个很小的区间，而不改变原有的大小覆盖关系，但是注意简单的离散化可能
会出现错误，给出下面两个简单的例子应该能体现普通离散化的缺陷:
例子一:1-10 1-4 5-10
例子二:1-10 1-4 6-10
普通离散化后都变成了[1,4][1,2][3,4]
线段2覆盖了[1,2],线段3覆盖了[3,4],那么线段1是否被完全覆盖掉了呢?
例子一是完全被覆盖掉了,而例子二没有被覆盖
解决的办法则是对于距离大于1的两相邻点，中间再插入一个点。
下面的离散化方法摘自别处（分不清哪位大佬是原创。。。反正不是本蒟蒻）：
解法：离散化，如下面的例子（题目的样例），因为单位1是一个单位长度，将下面的
1 2 3 4 6 7 8 10
— — — — — — — —
1 2 3 4 5 6 7 8
离散化 X[1] = 1; X[2] = 2; X[3] = 3; X[4] = 4; X[5] = 6; X[7] = 8; X[8] = 10
于是将一个很大的区间映射到一个较小的区间之中了，然后再对每一张海报依次更新在宽度为1~8的墙上(用线段树），最后统计不同颜色的段数。
但是只是这样简单的离散化是错误的，
如三张海报为：1~10 1~4 6~10
离散化时 X[ 1 ] = 1, X[ 2 ] = 4, X[ 3 ] = 6, X[ 4 ] = 10
第一张海报时：墙的1~4被染为1；
第二张海报时：墙的1~2被染为2，3~4仍为1；
第三张海报时：墙的3~4被染为3，1~2仍为2。
最终，第一张海报就显示被完全覆盖了，于是输出2，但实际上明显不是这样，正确输出为3。
新的离散方法为：在相差大于1的数间加一个数，例如在上面1 4 6 10中间加5（算法中实际上1，4之间，6，10之间都新增了数的）
X[ 1 ] = 1, X[ 2 ] = 4, X[ 3 ] = 5, X[ 4 ] = 6， X[ 5 ] = 10
这样之后，第一次是1~5被染成1；第二次1~2被染成2；第三次4~5被染成3
最终，1~2为2，3为1，4~5为3，于是输出正确结果3。
解这题特意去看了下STL中的unique函数（from：https://www.cnblogs.com/wangkundentisy/p/9033782.html）
unique函数属于STL中比较常用函数，它的功能是元素去重。即”删除”序列中所有相邻的重复元素(只保留一个)。
此处的删除，并不是真的删除，而是指重复元素的位置被不重复的元素给占领了。由于它”删除”的是相邻的重复元素，所以在使用unique函数之前，一般都会将目标序列进行排序。
unique函数的函数原型如下：
只有两个参数，且参数类型都是迭代器：
iterator unique(iterator it_1,iterator it_2);
这种类型的unique函数是我们最常用的形式。其中这两个参数表示对容器中[it_1，it_2)范围的元素进行去重(注：区间是前闭后开，即不包含it_2所指的元素),返回值是一个迭代器，它指向的是去重后容器中不重复序列的最后一个元素的下一个元素。
unique函数通常和erase函数一起使用，来达到删除重复元素的目的。(注：此处的删除是真正的删除，即从容器中去除重复的元素，容器的长度也发生了变换；而单纯的使用unique函数的话，容器的长度并没有发生变化，只是元素的位置发生了变化)
1 #include <stdio.h> 2 #include <string.h> 3 #include <iostream> 4 #include <string> 5 #include <math.h> 6 #include <algorithm> 7 #include <vector> 8 #include <queue> 9 #include <set> 10 #include <map> 11 #include <math.h> 12 const int INF=0x3f3f3f3f; 13 typedef long long LL; 14 const int mod=1e9+7; 15 //const double PI=acos(-1); 16 const int maxn=100010; 17 using namespace std; 18 //ios::sync_with_stdio(false); 19 // cin.tie(NULL); 20 21 struct node 22 { 23 int l; 24 int r; 25 int color; 26 }SegTree[30010<<2]; 27 28 struct Segment 29 { 30 int l; 31 int r; 32 }A[10010]; 33 int B[30010]; 34 int vis[30010<<4]; 35 int T,n,tot,cnt,ans; 36 37 int init()//初始化，离散化 38 { 39 scanf("%d",&n); 40 tot=0;//tot为离散化的计数器 41 for(int i=1;i<=n;i++) 42 { 43 scanf("%d %d",&A[i].l,&A[i].r); 44 B[++tot]=A[i].l; 45 B[++tot]=A[i].r; 46 B[++tot]=A[i].r+1;//完善后的离散化多加的一点 47 } 48 sort(B+1,B+1+tot); 49 int len=unique(B+1,B+1+tot)-B-1;//去除重点，求出规格 50 for(int i=1;i<=n;i++)//重新算出每个贴纸的区间 51 { 52 A[i].l=lower_bound(B+1,B+1+len,A[i].l)-B; 53 A[i].r=lower_bound(B+1,B+1+len,A[i].r)-B; 54 } 55 return len; 56 } 57 58 void PushDown(int rt) 59 { 60 if(SegTree[rt].color!=-1) 61 { 62 SegTree[rt<<1].color=SegTree[rt].color; 63 SegTree[rt<<1|1].color=SegTree[rt].color; 64 SegTree[rt].color=-1; 65 } 66 } 67 68 void Build(int l,int r,int rt) 69 { 70 SegTree[rt].l=l; 71 SegTree[rt].r=r; 72 SegTree[rt].color=0; 73 if(l==r) 74 { 75 return; 76 } 77 int mid=(l+r)>>1; 78 Build(l,mid,rt<<1); 79 Build(mid+1,r,rt<<1|1); 80 } 81 82 void Update(int L,int R,int color,int rt) 83 { 84 int l=SegTree[rt].l; 85 int r=SegTree[rt].r; 86 if(L<=l&&R>=r) 87 { 88 SegTree[rt].color=color; 89 return ; 90 } 91 PushDown(rt); 92 int mid=(l+r)>>1; 93 if(L<=mid) 94 Update(L,R,color,rt<<1); 95 if(R>mid) 96 Update(L,R,color,rt<<1|1); 97 } 98 99 void Query(int L,int R,int rt) 100 { 101 if(SegTree[rt].color!=-1) 102 { 103 if(!vis[SegTree[rt].color]) 104 { 105 ans++; 106 vis[SegTree[rt].color]=1; 107 } 108 return; 109 } 110 Query(L,R,rt<<1); 111 Query(L,R,rt<<1|1); 112 } 113 114 int main() 115 { 116 scanf("%d",&T); 117 while(T--) 118 { 119 int len=init(); 120 cnt=0;//区间染色时的计数器 121 Build(1,len,1);//建树 122 for(int i=1;i<=n;i++)//染色 123 { 124 Update(A[i].l,A[i].r,++cnt,1); 125 } 126 memset(vis,0,sizeof(vis)); 127 ans=0; 128 vis[0]=1; 129 Query(1,len,1); 130 printf("%d\n",ans); 131 } 132 return 0; 133 }
据说可以用Chtholly Tree珂朵莉树做，反正我不会。。。
珂朵莉树详解:https://www.luogu.org/blog/ACdreamer/chtholly-tree
该题的ODT做法可在这里找https://www.luogu.org/problemnew/solution/UVA10587
POJ-2528 Mayor's posters（线段树区间更新+离散化）
原文：https://www.cnblogs.com/jiamian/p/11397481.html