题目链接：poj2528
学习离散化的一个好题。。。
/*poj 2258 Mayor's posters 离散化，成段覆盖 题目大意： 不断的有海报覆盖在以前的海报上，求能看到几张海报 思路： 因为数据范围是1~10^7，所以需要离散化 首先依次读入线段端点坐标，存于pos[N][2]中， pos[i][0]存第一条线段的起点，pos[i][1]存第一条线段的终点， 然后用一个结构题数组line[N]记录信息，line[i].val记录端点坐标， line[i].num记录这个点属于哪条线段（可以用正负数表示， 负数表示起点，正数表示终点）。 假如有m条线段，就有2*m个端点。然后将line数组排序， 按照端点的坐标，从小到大排。接着要把线段赋予新的端点坐标了。 从左到右按照递增的次序，依次更新端点，假如2*m个点中， 共有tot个不同坐标的点，那么线段树的范围就是[1,tot]。 */ #include#include #include using namespace std; #define N 10010 int n; int a[N]; int pos[N][2]; struct node { int l,r,color; }s[N*5];//开4*N没过 struct date { int num,val; }line[N<<1]; bool cmp(date x, date y) { return x.val < y.val; } void build(int l, int r, int n) { s[n].l = l; s[n].r = r; s[n].color = -1; if(l == r) return; int mid = (l + r) >> 1; build(l, mid, n<<1); build(mid+1, r, n<<1|1); } void update(int l, int r, int n, int color) { if(s[n].color == color) return; if(s[n].l == l && s[n].r == r) { s[n].color = color; return; } if(s[n].color != -1) { s[n<<1].color = s[n<<1|1].color = s[n].color; s[n].color = -1; } int mid = (s[n].l + s[n].r) >> 1; if(r <= mid) update(l, r, n<<1, color); else if(l > mid) update(l, r, n<<1|1, color); else { update(l, mid, n<<1, color); update(mid + 1, r, n<<1|1, color); } } void query(int n) { if(s[n].color != -1) { a[s[n].color] = 1; return; } query(n<<1); query(n<<1|1); } int main() { int i,T,m; scanf("%d",&T); while(T--) { scanf("%d",&m); for(i = 0; i < m; i ++)//离散化 { scanf("%d%d",&pos[i][0],&pos[i][1]); line[i<<1].val = pos[i][0]; line[i<<1].num = i+1; line[i<<1|1].val = pos[i][1]; line[i<<1|1].num = -(i+1); } sort(line, line + 2*m,cmp); int tot = 1,temp = line[0].val; for(i = 0; i < 2*m; i ++) { if(line[i].val != temp) { tot++; temp = line[i].val; } if(line[i].num > 0) pos[line[i].num-1][0] = tot; else pos[-line[i].num-1][1] = tot; } build(1, tot, 1); for(i = 0; i < m; i ++) update(pos[i][0], pos[i][1], 1, i); memset(a, -1, sizeof(a)); query(1); int ans = 0; for(i = 0; i < m; i ++) if(a[i] >= 0) ans++; printf("%d\n",ans); } return 0; }