poj2528Mayor'sposters

/*

题意:往区间[1,10000000]的墙上贴海报&＃xff0c;海报数量<&＃61;10000&＃xff0c;
海报之间彼此可以覆盖&＃xff0c;问最后能看到的海报数量。

考虑到区间太大,直接线段树无疑会MLE,所以要对其离散化&＃xff0c;再用线段树。
基本做法是先对所有端点坐标进行排序&＃xff0c;用相应序号代替端点坐标构造线段树进行计算。
这样最大的序号也只是2*10000&＃xff0c;这样就减少了没必要的搜索的时间和内存空间。
同时为了提高效率&＃xff0c;采取倒插入的方式&＃xff0c;即从数据的最后一行开始处理&＃xff0c;在插入的同时进行判断。
在统计覆盖的时候&＃xff0c;采用倒插入的方式从树的根开始进行统计

*/

#include // 线段树&＃43;离散化
#include
using namespace std;
int cmp(const void *a,const void *b)
{
return *(int *)a-*(int *)b;
}
struct segment
{
int l,r;
int cover; //该区间已被覆盖的长度
}tree[80000];

int origin[80000][2]; //原始输入数据
bool vis[10000010]; //标记origin数组的元素是否已被处理

int arr[80000]; //离散化前的元素记录
int Hash[10000010]; //离散化后的元素记录

void BuildTree(int n,int s,int t)
{
tree[n].l&＃61;s;
tree[n].r&＃61;t;
tree[n].cover&＃61;0;
if(s
{
int mid&＃61;(s&＃43;t)/2;
BuildTree(2*n,s,mid);
BuildTree(2*n&＃43;1,mid&＃43;1,t);
}
}

int insert(int n,int s,int t) //若在范围[s,t]内可以找到空白的区域,则这张海报是可见的&＃xff0c;返回1
{
if(tree[n].cover&＃61;&＃61;tree[n].r-tree[n].l&＃43;1) //区间已全部被覆盖
{
return 0;
}
else //区间还有尚未被覆盖的地方
{
if(s&＃61;&＃61;tree[n].l&&t&＃61;&＃61;tree[n].r) //参数刚好是整个区间,所以肯定可以找到尚未被覆盖的地方
{
tree[n].cover&＃61;tree[n].r-tree[n].l&＃43;1;
return 1;
}
else //参数不是整个区间&＃xff0c;则要继续搜索孩子结点
{
int ok&＃61;0;
int mid&＃61;(tree[n].l&＃43;tree[n].r)>>1;
if(t<&＃61;mid)
{
if(insert(2*n,s,t)) //继续搜索左孩子
ok&＃61;1;
}
else if(s>&＃61;mid&＃43;1)
{
if(insert(2*n&＃43;1,s,t)) //继续搜索右孩子
ok&＃61;1;
}
else //区间横跨左右孩子,分段搜索左右孩子
{
if(insert(2*n,s,mid)) //找到任何一段空白的都可以
ok&＃61;1;
if(insert(2*n&＃43;1,mid&＃43;1,t))
ok&＃61;1;
}
tree[n].cover&＃61;tree[2*n].cover&＃43;tree[2*n&＃43;1].cover; //更新覆盖情况
return ok;
}
}
}

int main()
{
int cases,i;
scanf("%d",&cases);
while(cases--)
{
int num,rear&＃61;0;
scanf("%d",&num);
for(i&＃61;1;i<&＃61;num;&＃43;&＃43;i)
{
scanf("%d%d",&origin[i][0],&origin[i][1]);
if(!vis[origin[i][0]]) //保证arr数组中元素惟一
{
arr[&＃43;&＃43;rear]&＃61;origin[i][0];
vis[origin[i][0]]&＃61;true;
}
if(!vis[origin[i][1]])
{
arr[&＃43;&＃43;rear]&＃61;origin[i][1];
vis[origin[i][1]]&＃61;true;
}
}
qsort(arr&＃43;1,rear,sizeof(arr[1]),cmp); //升序排序

//离散化过程
for(i&＃61;1;i<&＃61;rear;&＃43;&＃43;i)
{
vis[arr[i]] &＃61; false; //重新对vis数组置为false
Hash[arr[i]]&＃61;i;
}
BuildTree(1,1,rear); //离散化后结点下标[1-rear]
int ans&＃61;0;
for(i&＃61;num;i>&＃61;1;--i)
{
if(insert(1,Hash[origin[i][0]],Hash[origin[i][1]]))
ans&＃43;&＃43;;
}
printf("%d\n",ans);
}
return 0;
}