|
题目传送门
题意：
一共有n张海报，可以贴在长度为10000000 的墙上，按顺序给出张贴的海报的区间，后贴的海报可以覆盖已经贴上的海报，问最后能看见的海报的数目。
思路分析：
以海报张贴的顺序给海报标记，然后每张贴一张海报就用线段树标记这个区间记录下是第几张海报，如果之前已经有海报被贴上了，就更新这个区间为新的海报，算是比较直接的想法。然后对于题目所给的墙的长度虽然很大，但是海报的张数最多只有1000张，所以我们需要对题目给出的区间的值进行离散化压缩空间。之后对于区间的维护，将区间换新一种海报后并不会对父节点产生什么影响，所以就不需要考虑up了。只需要在每次对已经覆盖的区间down就行了。
离散化：
这里简单介绍一下离散化（虽然也是为了写这题刚学就是了）
离散化，就是当我们只关心数据的大小关系时，用排名代替原数据进行处理的一种预处理方法。离散化本质上是一种哈希，它在保持原序列大小关系的前提下把其映射成正整数。当原数据很大或含有负数、小数时，难以表示为数组下标，一些算法和数据结构（如BIT）无法运作，这时我们就可以考虑将其离散化。
简单来说就是排序加二分后构造出的一个特殊的桶，虽然存的不是与下标相应的值，但是可以存放这个数在原序列中的相对大小，利用二分查找只需要log级别的时间复杂度。
举个栗子：
对于原区间a：1 2 4 8 10
离散化后我们可以得到b: 1 2 3 4 5
其中b[1]=1,b[2]=2,b[3]=4,b[4]=8,b[5]=10;
这样我们就可以将原来需要维护[1,10]的区间变为只需要维护[1,5]的区间了。?
利用STL大法的话就能很容易的实现了。
AC代码：
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<math.h>
#include<vector>
#include<queue>
#define INF 0x3f3f3f
#define ll long long
#define fre() freopen(".in", "r", stdin);freopen(".out", "w", stdout);
using namespace std;
#define lnode node<<1
#define rnode node<<1|1
const double eps = 1e-6;
const int N = 1e4 + 10;
const int mod = 1e9 + 7;
int n;
struct tree {
int l, r,col;
int mid(){
return l+r>>1;
}
} t[N << 4];//开大点总没错（bushi）
struct hb{
int l,r;
}s[N];//记录每个海报的区间
int p[N<<1];//离散化
bool v[N]; //记录颜色
void down(int node){//下传数据，如果当前区间有贴海报，就传给子区间
t[lnode].col=t[rnode].col=t[node].col;
t[node].col=0;
}
void build(int node, int l, int r) {//正常建树
t[node].l=l;t[node].r=r;t[node].col=0;
if (l == r) return ;//因为没什么需要初始化的，直接return了
int mid = (l + r) >> 1;
build(node << 1, l, mid);
build(node << 1 | 1, mid + 1, r);
}
void change(int node, int x, int y, int k) {//修改区间为后面贴的海报
if (x <= t[node].l && y >= t[node].r ) {
t[node].col=k;
return ;
}
if(t[node].col) down(node);//如果当前区间有贴海报才下传否则没必要
int mid = (t[node].r + t[node].l) >> 1;
if (x <= mid)change(node << 1, x, y, k);
if(y>mid) change(node << 1 | 1, x, y, k);
}
void ask(int node,int l ,int r) {//查询，遍历一次线段树，把存在的颜色都记录下来
if(t[node].l==t[node].r && t[node].col==0)return ;
if (t[node].col ) {
v[t[node].col]=1;
return ;
}
int mid = (t[node].r + t[node].l) >> 1;
ask(node << 1, t[node].l, mid);
ask(node << 1 | 1, mid+1, t[node].r);
}
int main() {
int T,ans=0;
cin >> T;
while (T--){
ans=0;
int cnt=0;memset(v,0,sizeof(v));
scanf("%d",&n);
for(int i=1;i<=n;i++){
int l,r;
scanf("%d%d",&l,&r);
p[++cnt]=l;p[++cnt]=r;//记录每个区间长度
s[i].l=l;s[i].r=r;
}
sort(p+1,p+cnt+1);//排序
int len=unique(p+1,p+cnt+1)-p-1;//离散化 STL大法
// for(int i=1;i<=len;i++)printf("p[%d]=%d ",i,p[i]);cout<<endl;//调试 离散化后的数组
build(1,1,len);//建树
for(int i=1;i<=n;i++){
s[i].l=lower_bound(p+1,p+len+1,s[i].l)-p;
s[i].r=lower_bound(p+1,p+len+1,s[i].r)-p;
//转换成离散化后的值进行区间修改
change(1,s[i].l,s[i].r,i);
}
// for(int i=1;i<=len<<1;i++)printf("t[%d] [%d,%d] col=%d \n",i,t[i].l,t[i].r,t[i].col);
ask(1,1,len);//遍历
for(int i=1;i<=n;i++){//记录颜色总数
if(v[i])ans++;
}
cout<<ans<<endl;//输出
}
return 0;
}
|