Description
The citizens of Bytetown, AB, could not stand that the candidates in the mayoral election campaign have been placing their electoral posters at all places at their whim. The city council has finally decided to build an electoral wall for placing the posters and introduce the following rules:
- Every candidate can place exactly one poster on the wall.
- All posters are of the same height equal to the height of the wall; the width of a poster can be any integer number of bytes (byte is the unit of length in Bytetown).
- The wall is divided into segments and the width of each segment is one byte.
- Each poster must completely cover a contiguous number of wall segments.
They have built a wall 10000000 bytes long (such that there is enough place for
all candidates). When the electoral campaign was restarted, the candidates were
placing their posters on the wall and their posters differed widely in width.
Moreover, the candidates started placing their posters on wall segments already
occupied by other posters. Everyone in Bytetown was curious whose posters will
be visible (entirely or in part) on the last day before elections.
Your task is to find the number of visible posters when all the posters are
placed given the information about posters' size, their place and order of
placement on the electoral wall.
Input
The first line of input contains a number c giving the number of cases that follow. The first line of data for a single case contains number 1 <= n <= 10000. The subsequent n lines describe the posters in the order in which they were placed. The i-th line among the n lines contains two integer numbers l i and ri which are the number of the wall segment occupied by the left end and the right end of the i-th poster, respectively. We know that for each 1 <= i <= n, 1 <= l i <= ri <= 10000000. After the i-th poster is placed, it entirely covers all wall segments numbered l i, l i+1 ,... , ri.
Output
For each input data set print the number of visible
posters after all the posters are placed.
The picture below illustrates the case of the sample input.
Sample Input
1
5
1 4
2 6
8 10
3 4
7 10
Sample Output
4
题意就是一块公告牌，长度为n。大家向上面依次贴广告，广告的范围是[L,R]，问你最后你在公告牌上能看见几个广告。
这个题分为3个阶段解！
显然是线段树啊！对！这是第一阶段！但如果硬写这个数据量不是TLE就是MLE。所以必须加上离散化处理。离散化处理就是这个题的第二阶段！
什么是离散化呢？就是建树时没有必要每个区间长度为1的区间都要占一个节点，这样无论在空间还是在以后的操作上面都是吃亏的。我们只需要存所有出现的区间的端点就可以了。
比如这个例子
3
1 10
1 4
6 10
我们把出现的端点排序然后去重以后得到的1,4,6,10。
1 4
6 10
↓ ↓ ↓ ↓
1 2
3 4
经过这样的一映射，我们就只处理一个长度为4的线段树就行了
结果显然是不对的,这个测试用例的结果是3，而如果向上面（普通离散化）这样分析的话结果就是2了，不信看下图。
是不是少了[4,5]这个区间？现在就要来到这个题的第三点！！！我们在普通离散化后，如果两个相邻的区间端点之差大于1，我们就再这两个端点间加一个端点。
像上面的用例就应该变成
1 3 4 5 6 9 10 我们都加上了一个右端点-1的三个点，在建树的时候考虑7个点
↓ ↓ ↓ ↓ ↓ ↓ ↓
1 2 3 4 5 6 7
这样建树就是对的！！！！！
代码如下：
1 #include <cstdio> 2 #include <algorithm> 3 #include <cstring> 4 using namespace std; 5 #define M 10010 6 bool hash[M]; 7 int col[M<<4];//用来保存颜色（海报） 8 struct segTree 9 { 10 int l,r; 11 }tree[M]; 12 int ans,x[M<<2],n,t; 13 void PushDown (int now)//如果当前节点有海报，向下更新 14 { 15 if (col[now]!=-1) 16 { 17 col[now<<1]=col[now<<1|1]=col[now]; 18 col[now]=-1; 19 } 20 } 21 void Update (int L,int R,int c,int l,int r,int now) 22 { 23 if (L<=l&&r<=R)//如果正好找到区间，修改区间 24 { 25 col[now]=c; 26 return ; 27 } 28 PushDown(now);//延迟后的更新（这时候该用子节点了，要向下更新） 29 int m=(l+r)>>1; 30 if (L<=m) 31 Update(L,R,c,l,m,now<<1); 32 if (R>m) 33 Update(L,R,c,m+1,r,now<<1|1); 34 } 35 void query (int l,int r,int now) 36 { 37 if (col[now]!=-1) 38 { 39 if (!hash[col[now]]) 40 ans++; 41 hash[col[now]]=true; 42 return ; 43 } 44 if (l==r)//更新到底一定要return，要不会炸 45 return ; 46 int m=(l+r)>>1; 47 query(l,m,now<<1); 48 query(m+1,r,now<<1|1); 49 } 50 int main() 51 { 52 //freopen("de.txt","r",stdin); 53 scanf("%d",&t); 54 while (t--) 55 { 56 int cnt=0; 57 scanf("%d",&n); 58 for (int i=0;i<n;++i) 59 { 60 scanf("%d%d",&tree[i].l,&tree[i].r); 61 x[cnt++]=tree[i].l,x[cnt++]=tree[i].r; 62 } 63 sort(x,x+cnt); 64 int m=1; 65 for (int i=1;i<cnt;++i) 66 if (x[i]!=x[i-1]) x[m++]=x[i];//记录不重复的节点 67 for (int i=m-1;i>=1;--i) 68 if (x[i]!=x[i-1]+1) x[m++]=x[i-1]+1;//把相差大于1的两个节点之间再加上一个节点（右节点-1） 69 sort(x,x+m); 70 memset(col,-1,sizeof col); 71 for (int i=0;i<n;++i) 72 { 73 int l=lower_bound(x,x+m,tree[i].l)-x; 74 int r=lower_bound(x,x+m,tree[i].r)-x; 75 Update(l,r,i,0,m,1); 76 } 77 memset(hash,false,sizeof hash); 78 ans=0; 79 query(0,m,1); 80 printf("%d ",ans); 81 } 82 return 0; 83 }
这个题去重的时候办法可能老土，但是别用set！！！不信看时间！不用set 79ms 用了set 375ms
