poj2528 Mayor’s posters
题意:在墙上贴海报,海报可以互相覆盖,问最后可以看见几张海报
思路:这题数据范围很大,直接搞超时+超内存,需要离散化:
离散化简单的来说就是只取我们需要的值来用,比如说区间[1000,2000],[1990,2012]
我们用不到[-∞,999][1001,1989][1991,1999][2001,2011][2013,+∞]这些值,所以我只需要1000,1990,2000,2012就够了,将其分别映射到0,1,2,3,在于复杂度就大大的降下来了
所以离散化要保存所有需要用到的值,排序后,分别映射到1~n,这样复杂度就会小很多很多
而这题的难点在于每个数字其实表示的是一个单位长度(并非一个点),这样普通的离散化会造成许多错误(包括我以前的代码,poj这题数据奇弱)
例子一: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是否被完全覆盖掉了呢?
例子一是完全被覆盖掉了,而例子二没有被覆盖
为了解决这种缺陷,我们可以在排序后的数组上加些处理,比如说[1,2,6,10]
如果相邻数字间距大于1的话,下标位置向后延一下就行了 。。。比如说6是排名第三位的，我把它排名到第四位就好了。这个原理应该不难想出来的。
为了解决这种缺陷,我们可以在排序后的数组上加些处理,比如说[1,2,6,10]
如果相邻数字间距大于1的话,在其中加上任意一个数字,比如加成[1,2,3,6,7,10],然后再做线段树就好了.
线段树功能:update:成段替换 query:简单hash
线段树成段更新。查询的时候，实际上是二分遍历整个查询区间，每一个单位用vis来标记是否访问过。然后用D[x]来识别是否整个区间是连续的。
先不考虑离散化的问题。关于Update，我觉得本身它的Pushdown操作中携带本身题目要求的覆盖的成分，所以Pushdown是必须的。而不需要Pushup。
针对于Query操作。网上很多的题解中都没有Pushdown，这是因为本身Update的某个区间肯定和Query的某个区间是相同的，万一不同，还是需要Pushdown的，所以我写了这个操作在Query里，也是能AC的，而且我觉得是必要的。
关于离散化，由于数据范围大，查询量少。所以离散化是必要的，没什么好说的。。但是有一点，很多人忽略了完全覆盖的问题，即便是AC代码也是这样，事实上，这是因为Poj这题的数据太弱了。。。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
#include <iostream> using namespace std;
#define Maxn 60005
#define lx (x<<1)
#define rx ((x<<1) | 1)
#define MID ((l + r)>>1)
struct Node
{
int val;
int id;
bool operator <(const Node &a) const
{
return val<a.val || (val == a.val && id<a.id);
}
}A[Maxn];
int D[Maxn<<2];
int vis[Maxn];
int rank[Maxn];
int t,n;
void init()
{
memset(D,0,sizeof(D));
memset(vis,0,sizeof(vis));
}
void pushDown(int x)
{
if(D[x])
{
D[lx] = D[rx] = D[x];
D[x] = 0;
}
}
int query(int L,int R,int l,int r,int x)
{
if(D[x])
{
if(!vis[D[x]]) //之前可能1张海报跨了很多区间，D[X]=d D[Y]=d 这里一次性就让 vis[d] =1 了 防止多次
{
vis[D[x]] = 1;
return 1;
}
return 0;
}
//我觉得这一步是必要的。即使对于本题没有作用，但是思路上要求我们要这么做。
//pushDown(x);
if(l == r) return 0;
int ans = 0;
if(L<=MID) ans += query(L,R,l,MID,lx);
if(MID+1<=R) ans +=query(L,R,MID+1,r,rx);
return ans;
}
void update(int d,int L,int R,int l,int r,int x)//延迟更新
{
if(L<=l && r<=R)
{
D[x] = d; //注意这里==d的原因
return; //如果存在区间更小的 大区间就要往下 相当于分割的效果
}
pushDown(x);
if(L<=MID) update(d,L,R,l,MID,lx);
if(MID+1<=R) update(d,L,R,MID+1,r,rx);
}
int main()
{
#ifndef ONLINE_JUDGE #endif
scanf(" %d",&t);
while(t--)
{
scanf(" %d",&n);
n *= 2;
for(int i=0;i<n;i++)
{
scanf(" %d",&A[i].val);
A[i].id = i;
}
sort(A,A+n);
int cnt = 1;
rank[A[0].id] = cnt;
int lastValue = A[0].val;//A[i].id存的是第几个
for(int i=1;i<n;i++)
{
if(A[i].val == lastValue) rank[A[i].id] = cnt;//rank[最小的那个值]=1 但是里面存的是之前第几个
//相邻数据如果相隔大于1，Rank向后延一位
else if(A[i].val - lastValue>1)
{
++cnt;
rank[A[i].id] = ++cnt;
lastValue = A[i].val;
}
else
{
rank[A[i].id] = ++cnt;
lastValue = A[i].val;
}
}
init();
for(int i=0;i<n/2;i++) update(i+1,rank[i<<1],rank[i<<1 | 1],1,cnt,1); // (1,rank[0],rank[1]) A[].id=0/1; 找到对应的cnt
int ans = query(1,cnt,1,cnt,1);
printf("%d\n",ans);
}
return 0;
}
版权声明：本文为博主原创文章，未经博主允许不得转载。