题目链接：[点击打开链接](http://poj.org/problem?id=2528) 题意：在墙上贴海报,海报可以互相覆盖,问最后可以看见几张海报。 该题是线段树区间修改+离散化的应用。 不难想到， 每次对一个最长10^7的线段进行线段树的区间修改， 最后统计。 线段树的复杂度是log10^7， 应该不会超时， 但是会超内存。 所以想到要离散化， 将区间端点值有映射成一个尽量小的值。 但是该题求的是覆盖情况， 如果按照单纯的点对点的离散化， 那样会出现错误答案。 例如：  依次贴[1,10], [1,3], [5,10] ， 离散化后1->1, 3->2, 5->3, 10->4 那么第一次让离散后的区间[1,4]变成1，第二次让[1,2]变成2，第三次让[3,4]变成3，那么最终答案成了2， 其实是3。 问题之所在就在于：小的区间不会覆盖大区间的所有部分。 解决方法就是在相邻区间端点大于1时再添加一个二者中间的数当作“空白”区域。 不会离散化的先学学离散化吧， 一般用二分来维护比较简单。 细节参见代码： ~~~ #include<cstdio> #include<cstring> #include<algorithm> #include<iostream> #include<string> #include<vector> #include<stack> #include<bitset> #include<cstdlib> #include<cmath> #include<set> #include<list> #include<deque> #include<map> #include<queue> #define Max(a,b) ((a)>(b)?(a):(b)) #define Min(a,b) ((a)<(b)?(a):(b)) using namespace std; typedef long long ll; const double PI = acos(-1.0); const double eps = 1e-6; const int INF = 1000000000; const int maxn = 11111; int T,n,ans,setv[maxn<<4],X[maxn<<3]; bool vis[maxn]; struct node { int l, r; node(int ll=0, int rr=0):l(ll), r(rr) {} bool operator < (const node& rhs) const { return l < rhs.l || (l == rhs.l && r < rhs.r); } }a[maxn]; void pushdown(int o) { if(setv[o]) { setv[o<<1] = setv[o<<1|1] = setv[o]; setv[o] = 0; } } void update(int L, int R, int v, int l, int r, int o) { int m = (l + r) >> 1; if(L <= l && r <= R) { setv[o] = v; return ; } pushdown(o); if(L <= m) update(L, R, v, l, m, o<<1); if(m < R) update(L, R, v, m+1, r, o<<1|1); } void query(int l, int r, int o) { int m = (l + r) >> 1; if(setv[o]) { if(!vis[setv[o]]) { vis[setv[o]] = true; ++ans; } return ; } if(l == r) return ; query(l, m, o<<1); query(m+1, r, o<<1|1); } int main() { scanf("%d",&T); while(T--) { scanf("%d",&n); int cnt = 0; for(int i=1;i<=n;i++) { scanf("%d%d",&a[i].l,&a[i].r); X[cnt++] = a[i].l; X[cnt++] = a[i].r; } sort(X, X+cnt); cnt = unique(X, X+cnt) - X; int m = cnt; for(int i=1;i<cnt;i++) { if(X[i] > X[i-1]+1) X[m++] = X[i] + 1; } sort(X, X + m); memset(vis, false, (n+1)*sizeof(vis[0])); memset(setv, 0, sizeof(setv)); for(int i=1;i<=n;i++) { int lc = lower_bound(X, X + m, a[i].l) - X + 1; int rc = lower_bound(X, X + m, a[i].r) - X + 1; update(lc, rc, i, 1, m, 1); } ans = 0; query(1, m, 1); printf("%d\n",ans); } return 0; } ~~~