POJ 2528(线段树 区间更新 离散化)

POJ 2528

题目大意

有一排分成若干组长为1区间的墙，现在要往墙上贴n张海报，一个海报覆盖连续的L到R的区间，按照一定的顺序贴，问最后有多少海报全部或有一部分漏在了表面。 (1≤L≤R≤107,n≤10000)

分析

由于L和R比较大但线段数目不大(最多出现20000种数字)，所以需要先对数据进行一下离散化，将L和R映射到一个较小的区间. 更新操作是将一个区间全部更改这个线段的编号，这样在进行n此更新后，对每一个点进行查询看这个点属于哪个线段，最后统计以下就是答案。

技巧

(以下内容引用自:数据的离散化) 使用STL算法离散化： 思路：先排序，再删除重复元素，然后就是索引元素离散化后对应的值。 假定待离散化的序列为a[n]，b[n]是序列a[n]的一个副本，则对应以上三步为：

sort(sub_a,sub_a+n); int size=unique(sub_a,sub_a+n)-sub_a;//size为离散化后元素个数 for(i=0;i<n;i++) a[i]=lower_bound(sub_a,sub_a+size,a[i])-sub_a + 1;//k为b[i]经离散化后对应的值

对于第3步，若离散化后序列为0, 1, 2, …, size - 1则用lower_bound，从1, 2, 3, …, size则用upper_bound，其中lower_bound返回第1个不小于b[i]的值的指针，而upper_bound返回第1个大于b[i]的值的指针，当然在这个题中也可以用lower_bound然后再加1得到与upper_bound相同结果，两者都是针对以排好序列。使用STL离散化大大减少了代码量且结构相当清晰。

代码

#include<cstdio> #include<iostream> #include<cmath> #include<cstring> #include<cstdlib> #include<queue> #include<map> #include<algorithm> #include<set> #include<stack> const int MAXN=100005;//线段数 int n; int info[MAXN*4];//线段树维护的信息 int lenth; int bj[MAXN*2]; int num[MAXN*2];//用于保存离散化信息 int cnt; using namespace std; struct LINE { int a; int b; }line[MAXN]; void Init() { cnt=0; lenth=0; memset(bj,0,sizeof(bj)); memset(info,0,sizeof(info)); } void Pushdown(int rt)//下推延迟信息，该节点的信息已更新 { if(info[rt]) { info[rt*2]=info[rt]; info[rt*2+1]=info[rt]; info[rt]=0; } } void Update(int L,int R,int C,int l,int r,int rt)//保证(L,R)区间的数将会更新为C { if(L<=l && r<=R){info[rt]=C;return ;} int m=(l+r)/2; Pushdown(rt); if(L<=m)Update(L,R,C,l,m,rt*2); if(R>m)Update(L,R,C,m+1,r,rt*2+1); } int Query(int x,int l,int r,int rt)//查询第x个数是什么 { if(l==r)return info[rt]; int m=(l+r)/2; Pushdown(rt); if(x<=m)return Query(x,l,m,rt*2); else if(x>m)return Query(x,m+1,r,rt*2+1); } void Solve() { int t; int ans=0; for(int i=1;i<=lenth;i++) { t=Query(i,1,lenth,1); bj[t]=1; } for(int i=1;i<=lenth;i++)ans+=bj[i]; printf("%d\n",ans); } int main() { int T; int a,b; scanf("%d",&T); while(T--) { Init(); scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d%d",&a,&b); num[++cnt]=a; num[++cnt]=b; line[i].a=a;line[i].b=b; } sort(num+1,num+cnt+1); int m=unique(num+1,num+cnt+1)-num-1;//unique返回去重后尾地址，但那个地址不含数字，m表示去重后的个数 int t=m; for(int i=2;i<=t;i++)//如果两个数相差大于1则在他们之间插入一个数 { if(num[i]-num[i-1]>1) num[++m]=num[i-1]+1; } sort(num+1,num+m+1); int x,y; lenth=m; for(int i=1;i<=n;i++) { x=lower_bound(num+1,num+m+1,line[i].a)-num;//lower_bound返回第1个不小于line[i].a的值的指针 y=lower_bound(num+1,num+m+1,line[i].b)-num; Update(x,y,i,1,lenth,1); } Solve(); } return 0; }