设为首页 - 加入收藏 焦点技术网
热搜:java
当前位置:首页 >

POJ 2528 Mayor's posters 线段树成段更新+离散化

2014-05-01 22:05:00.0 数据结构  
导读:题目来源:POJ 2528 Mayor's posters题意:很多张海报贴在墙上 求可以看到几张海报 看那两张图就行了 第一张俯视图思路:最多2W个不同的数 离散化一下 然后成段更新 a[rt] = i代表这个区间是第i张报纸 更新玩之后一次query cover[i]=1代表可以看到第i张报纸#include #include #include using namespace std;cons...。。。

题目来源:POJ 2528 Mayor's posters

题意:很多张海报贴在墙上 求可以看到几张海报 看那两张图就行了 第一张俯视图

思路:最多2W个不同的数 离散化一下 然后成段更新 a[rt] = i代表这个区间是第i张报纸 更新玩之后一次query cover[i]=1代表可以看到第i张报纸

#include #include #include using namespace std;const int maxn = 20010;int a[maxn<<2];int cover[maxn<<2];struct Point{ int x, id, v;}b[maxn];int n;bool cmp1(Point a, Point b){ return a.x < b.x;}bool cmp2(Point a, Point b){ return a.id < b.id;}void build(int l, int r, int rt){ a[rt] = 0; //printf("%d %d\n", l, r); if(l+1 == r)  return; int m = (l + r) >> 1; build(l, m, rt<<1); build(m, r, rt<<1|1);}void update(int x, int y, int l, int r, int rt, int num){  if(l == x && r == y) {  a[rt] = num;  return; } int m = (l + r) >> 1; if(a[rt]) {  a[rt<<1] = a[rt];  a[rt<<1|1] = a[rt];  a[rt] = 0; } if(y <= m)  update(x, y, l, m, rt<<1, num); else if(x >= m)  update(x, y, m, r, rt<<1|1, num); else {  update(x, m, l, m, rt<<1, num);  update(m, y, m, r, rt<<1|1, num); }}void query(int l, int r, int rt){ if(l+1 == r || a[rt]) {   cover[a[rt]] = 1;  //printf("%d\n", a[rt]);  return; } int m = (l + r) >> 1; if(a[rt]) {  a[rt<<1] = a[rt];  a[rt<<1|1] = a[rt];  a[rt] = 0; } query(l, m, rt<<1); query(m, r, rt<<1|1);}int main(){ int T;  scanf("%d", &T); while(T--) {  scanf("%d", &n);  for(int i = 0; i < n; i++)  {   scanf("%d %d", &b[i<<1].x, &b[i<<1|1].x);   b[i<<1|1].x++;   b[i<<1].id = i<<1;   b[i<<1|1].id = i<<1|1;  }  sort(b, b+2*n, cmp1);  int now = b[0].x;  int sum = 1;  for(int i = 0; i < 2*n; i++)  {   if(b[i].x != now)   {    now = b[i].x;    sum++;   }   b[i].v = sum;  }  sort(b, b+2*n, cmp2);  //printf("%d\n", sum);  //memset(a, 0, sizeof(a));  build(1, sum, 1);  //puts("sdsf");  for(int i = 0; i < n; i++)  {   //printf("**%d %d\n", b[i<<1].v, b[i<<1|1].v);   update(b[i<<1].v, b[i<<1|1].v, 1, sum, 1, i+1);   //puts("ddsf");  }  memset(cover, 0, sizeof(cover));    query(1, sum, 1);  int ans = 0;  for(int i = 1; i <= n; i++)   if(cover[i])    ans++;  printf("%d\n", ans); } return 0;}


 

(编辑: u011686226)

网友评论
相关文章