题目链接： http://poj.org/problem?id=2528
题目描述： 在一个长度为maxn 的墙上贴海报， 海报按先后给出的顺序进行粘贴， 可以相互覆盖， 问最后可以露出几个海报(maxn <= 1e7)
解题思路：一开始读错题了.....以为是覆盖的最多数.....如果是这样的话就直接统计最大值就可以了。 后来读明白题， 但是1e7数组又开不下， 所以得离散化， 但是这里又遇到一个问题
给出下面两个简单的例子应该能体现普通离散化的缺陷:
例子一: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是否被完全覆盖掉了呢?
例子一是完全被覆盖掉了,而例子二没有被覆盖 转自http://blog.csdn.net/metalseed/article/details/8039326
解决方法是在两个相差不为1的节点之后在插入一个值， 再做线段树， 由于这里只关心不同布段出现的次数， 所以不需要pushup函数， 直接一个全局变量配合着hash表就可以
代码中有部分注释
代码：
#include <iostream> #include <cstdio> #include <string> #include <vector> #include <map> #include <cstring> #include <iterator> #include <cmath> #include <algorithm> #include <stack> #include <deque> #include <map> #define lson l, m, rt<<1 #define rson m+1, r, rt<<1|1 typedef long long LL; using namespace std; int cases; const int maxn = 1e5+100; bool hash1[maxn]; int li[maxn]; int ri[maxn]; int X[maxn*3]; int col[maxn<<4]; int cnt; void PushDown( int rt ) { if( col[rt] != -1 ) { col[rt<<1] = col[rt<<1|1] = col[rt]; col[rt] = -1; } } void update( int L, int R, int c, int l, int r, int rt ) { if( L <= l && r <= R ) { col[rt] = c; return; } PushDown(rt); int m = (l + r) >> 1; if( L <= m ) update( L, R, c, lson ); if( m < R ) update( L, R, c, rson ); } void query( int l, int r, int rt ) { if( col[rt] != -1 ) { if( !hash1[col[rt]] ) cnt++; hash1[col[rt]] = true; return; } if( l == r ) return; int m = (l + r) >> 1; query( lson ); query( rson ); } int Bin( int key, int n, int X[] ) { // Bin to find the value int l = 0; int r = n-1; while( l <= r ) { int m = (l + r) >> 1; if( X[m] == key ) return m; if( X[m] < key ) l = m + 1; else r = m-1; } return -1; } int main() { int t, n; scanf( "%d", &t ); while( t-- ) { scanf( "%d", &n ); int nn = 0; for( int i = 0; i < n; i++ ) { scanf( "%d%d", li+i, ri+i ); X[nn++] = li[i]; X[nn++] = ri[i]; } sort( X, X+nn ); int m = 1; for( int i = 1; i < nn; i++ ) { // unique if( X[i] != X[i-1] ) { X[m++] = X[i]; } } for( int i = m-1; i > 0; i-- ) { if( X[i] != X[i-1] +1 ) X[m++] = X[i-1] + 1; // deal with the drawback } sort( X, X+m ); memset(col, -1, sizeof(col)); for( int i = 0; i < n; i++ ) { int l = Bin(li[i], m, X); int r = Bin(ri[i], m, X); update( l, r, i, 0, m, 1 ); } cnt = 0; memset( hash1, false, sizeof( hash1) ); query(0, m, 1); printf( "%d ", cnt ); } return 0; }
思考： 自己第一次做不是裸的线段树， 还是有好多好多不熟练的地方， 决定按照之前转载的那篇博客先把那里的题目刷干净， 在自己去找题做， 线段树是个硬骨头， 不好啃， 需要一些耐心， 但是只要学明白线段树， 收益无穷。
今晚儿再做一道DP。。。。。。