异想天开

What's the true meaning of light, Could you tell me why

posters-线段树

日期:2015-02-13 15:05:56
  
最后更新日期:2015-07-14 13:59:42
【技术】
题目:
http://acm.nyist.net/JudgeOnline/problem.php?pid=9
分析:
线段树+离散化。该题之前写的超时,后来看资料说要用线段树,网上查找人家的做法,昨天码了一下,wa。后面修改程序过了下面的数据后:
3
3
5 6
4 5
6 8
3
1 10
1 3
6 10
5
1 4
2 6
8 10
3 4
7 10
就AC了。发现最大的问题还是离散化的问题。 首先离散是为了节约计算时间,比如若原数据点位1 2 3 4,则需要离散为1 2 3 4;另外一种情况就是1 2 3 1000,则需要离散为1 2 3 5。总体的离散思想是把间隙变小,而不是没有(最开始是想直接全变偶数,或全变奇数来离散,1 2 3 1000,变为1 3 5 7,则本来的连续关系改变了)。还有一个地方需要注意的就是线段树节点的个数,应该是节点个数的4倍,因为本来建线段树2倍,同时离散化最多两倍原来的节点个数,故最大需要4倍。
线段树:
假设[1-7]线段,建立线段树如下:
代码:
[code lang="cpp"]
#include<iostream>
#include<map>
#include<vector>
#include <algorithm>
#include<stdio.h>
#include<memory.h>
#include<set>

using namespace std;
// 10000个竞选人即10000条线段
const int MAX_PERSON = 10000+1 ;
//20000个端点
const int MAX_POINT = 2*MAX_PERSON ;
//线段树的节点,注意这里由于离散化和建线段树需要4倍节点个数
const int MAX_NODE = 2*2*MAX_POINT + 1;

struct poster{
int l,r; //海报左右边界
};
struct poster person[MAX_PERSON];
//线段树
struct node {
int l,r; //线段的边界
int c; //线段的颜色
int flag; //是否为同色
};
struct node segtree[MAX_NODE];
//建树过程
void build(int p, int l ,int r){
segtree[p].l=l;
segtree[p].r=r;
segtree[p].c=0;
segtree[p].flag=0;
if( l==r ){
return;
}
int mid=(l+r)/2;
build(2*p,l,mid);
build(2*p+1,mid+1,r);
}
//贴海报过程
// node 表示线段树的节点
// pl,pr表示海报的左边界与右边界
void update(int p,int node,int pl,int pr){
//左边界等于右边界或到了叶子节点
if( (segtree[node].l==pl && segtree[node].r==pr) \
|| (segtree[node].l == segtree[node].r) ){
segtree[node].c = p;
segtree[node].flag=1; //标记区间颜色相同
return;
}
//节点纯色,但贴的海报颜色不一致
if( segtree[node].flag && segtree[node].c!=p ){
segtree[2*node].flag=segtree[2*node+1].flag=1;
segtree[2*node].c=segtree[2*node+1].c=segtree[node].c;
segtree[node].flag=0;
}
int mid=(segtree[node].l+segtree[node].r)/2;
if(pr<=mid){
update(p,2*node,pl,pr);
}else if (pl>mid){ //这里要大于,mid节点是算右节点
update(p,2*node+1,pl,pr);
}else {
update(p,2*node,pl,mid);
update(p,2*node+1,mid+1,pr);
}
//左右子树纯色且同色
if( segtree[2*node].flag && segtree[2*node+1].flag \
&& (segtree[2*node].c==segtree[2*node+1].c) ){
segtree[node].flag=1;
segtree[node].c=segtree[2*node].c;
}
}

int my_less(int i,int j){
return i<j;
}

set<int> tmp_set;
map<int,int> indx;
vector<int> tmp_vec;

void query(int node){
if( segtree[node].flag || segtree[node].l==segtree[node].r ){
if( segtree[node].c !=0 ){
tmp_set.insert(segtree[node].c);
}
return;
}
query(2*node);
query(2*node+1);
}

int main()
{
int c,n;
scanf("%d",&c);
while(c-->0){
//离散化用到的数据结构
tmp_vec.clear();
indx.clear();
tmp_set.clear();
scanf("%d",&n);
for( int i=1;i<=n;i++ ){
scanf("%d %d",&person[i].l,&person[i].r);
tmp_vec.push_back(person[i].l);
tmp_vec.push_back(person[i].r);
}
sort(tmp_vec.begin(),tmp_vec.end(),my_less);
vector<int>::iterator iter,iter_end ;
iter_end = unique(tmp_vec.begin(),tmp_vec.end());
//这里离散,如果是1 2 3 4这样连续的则离散为1 2 3 4,
//若为1 3 4 7 则离散为1 3 4 6
int val_end=1,pre=-1;
for( iter=tmp_vec.begin();iter!=iter_end;iter++ ){
if( *iter==pre){
val_end--;
}
pre=*iter+1;
indx[*iter]=val_end;
val_end += 2;
}
//val_end--;
//cout<<"val_end:"<<val_end<<endl;
//初始化,线段树,线段树的初始值为0,表示没有贴任何海报或没有完全覆盖
//线段树的节点最大个数为叶子节点的2倍,因为一个叶子节点只有一个父节点,但父节点会有重复的
build(1,1,val_end);
for(int i=1; i<=n; i++){
int l_indx = indx[person[i].l];
int r_indx = indx[person[i].r];
//cout<<l_indx<<" "<<r_indx<<endl;
update(i,1,l_indx,r_indx);
}
query(1);
cout<<tmp_set.size()<<endl;
}
return 0;
}
[/code]