对于这道题首先要用到离散化的知识，但是离散化并非常规的离散化。
离散化，如下面的例子（题目的样例），因为单位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。
至于贴海报， 要倒着思考 注意线段树开的空间大小。poj用c++过不了，用G++可以过，不知道为什么
关于离散化的一个叫做区间离散化的东西也很容易出错需要注意。
#include<iostream> #include<string> #include <cstdlib> #include <algorithm> #include<cmath> #include<cstring> #include<cstdio> #include<vector> #include<queue> #include<map> #include<set> #include<bitset> #include <iomanip> // #pragma comment(linker, "/STACK:1024000000,1024000000") // #define pi acos(-1) // #include<bits/stdc++.h> using namespace std; typedef long long ll; #define INF 0x7f7f7f7f //2139062143 #define INF1 0x3f3f3f3f //1061109567 #define INF2 2147483647 #define llINF 9223372036854775807 #define pi 3.141592653589793//23846264338327950254 #define pb push_back #define ll long long #define debug cout << "debug "; // freopen(".in","r",stdin); // freopen(".out","w",stdout); // ios::sync_with_stdio(false);cin.tie(NULL); #define scai(x) scanf("%d", &x) #define sca2i(x, y) scanf("%d %d", &x, &y) #define scaf(x) scanf("%lf", &x) #define sca2f(x, y) scanf("%lf %lf", &x, &y) #define For(m,n) for (int i = m; i < n; i++) #define local #ifdef local #endif #define MAX 10233 #define LCH(i) ((i) << 1) #define RCH(i) ((i) << 1 | 1) int X[MAX][2]; int lsh[MAX<<1]; struct node { int l, r; int lazy; }tree[MAX<<3]; void build(int rt, int l, int r) { // debug tree[rt].l = l; tree[rt].r = r; tree[rt].lazy = 0; if (l == r) { return; } int mid = (l + r) >> 1; build(rt<<1, l, mid); build(rt<<1|1, mid + 1, r); } bool updata(int rt, int l, int r) { if (tree[rt].lazy) { return false; } else if (tree[rt].l == l && tree[rt].r == r) { tree[rt].lazy = 1; return true; } int mid = (tree[rt].l + tree[rt].r) >> 1; bool flag; if (r <= mid) { flag = updata(rt<<1, l, r); } else if (l > mid) { flag = updata(rt<<1|1, l, r); } else { bool flag1 = updata(rt<<1, l, mid); bool flag2 = updata(rt<<1|1, mid + 1, r); flag = flag1 || flag2; } if (tree[rt << 1].lazy == 1 && tree[rt << 1|1].lazy == 1) tree[rt].lazy = 1; return flag; } int main() { int Case; scanf("%d ", &Case); while(Case--) { int n; scanf("%d", &n); int k = 0; for (int i = 0; i < n; i++) { scanf("%d%d", &X[i][0], &X[i][1]); lsh[k++] = X[i][0]; lsh[k++] = X[i][1]; } sort(lsh, lsh + k); int size = unique(lsh, lsh + k) - lsh; k = size; for (int i = 0; i < size; i++) { if (lsh[i] - lsh[i-1] > 1) lsh[k++] = lsh[i] + 1; } size = k; sort(lsh, lsh + size); build(1, 0, size - 1); int ans = 0; for (int i = n-1; i >= 0; i--) { int l = lower_bound(lsh, lsh + size, X[i][0]) - lsh; int r = lower_bound(lsh, lsh + size, X[i][1]) - lsh; if (updata(1, l, r)) ans++; } printf("%d ", ans); } }