校门外的树 Plus Plus(0764)
问题描述
西南某科技大学的校门外长度为 L 的公路上有一排树，每两棵相邻的树之间的间隔都是 1 米。我们可以把马路看成一个数轴，马路的一端在数轴 1 的位置，另一端在 L 的位置；数轴上的每个整数点，即 1，2，……，L，都种有一棵树。
现在要将这排树的某一段涂成某种颜色，给定 N 组区间[ J,K ]，表示从 J 到 K 的树都要涂上一种颜色（每次涂的颜色不一样,而且每次涂色会覆盖掉原来的颜色），区间之间可能有重叠的部分, L 的长度为 1000,0000。现在你的任务是计算涂色工作结束后，这一排树里总共有多少种颜色的树？（没涂过色的不算）
输入
第一行为一个整数N （1<=N<=10000）。 接下来的N行每行是两个整数数J，K（1<=J<=K<=1000,0000），表示涂色的起止区间。
多组测试数据。
输出
一个整数，表示有多少种颜色的树。
样例输入
2
1 10
5 5
1
1 1
样例输出
21 线段树可解
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 40005struct tree
{
int l,r;
}p[N<<];int tot;
int ans;
int x[N];
int lazy[N<<];
bool flag[N<<];void pushdown(int rt)
{
if(lazy[rt]!=-)
{
lazy[rt<<]=lazy[rt<<|]=lazy[rt];
lazy[rt]=-;
}
}
void build(int l,int r,int rt)
{
lazy[rt]=-;
if(l==r) return;
int m=(l+r)>>;
build(l,m,rt<<);
build(m+,r,rt<<|);
}
void update(int l,int r,int rt,int L,int R,int c)
{
if(l==L && R==r)
{
lazy[rt]=c;
return;
}
pushdown(rt);
int m=(l+r)>>;
if(R<=m) update(l,m,rt<<,L,R,c);
else if(L>m) update(m+,r,rt<<|,L,R,c);
else
{
update(l,m,rt<<,L,m,c);
update(m+,r,rt<<|,m+,R,c);
}
}
void query(int l,int r,int rt)
{
if(lazy[rt]!=-)
{
if(!flag[lazy[rt]])
{
ans++;
flag[lazy[rt]]=;
}
return;
}
if(l>=r) return;
pushdown(rt);
int m=(l+r)>>;
query(l,m,rt<<);
query(m+,r,rt<<|);
}
int main()
{
int n,i;
while(scanf("%d",&n)!=EOF)
{
ans=;
tot=;
memset(flag,,sizeof(flag));
for(i=;i<n;i++)
{
scanf("%d%d",&p[i].l,&p[i].r);
x[tot++]=p[i].l;
x[tot++]=p[i].r;
} sort(x,x+tot);
tot=unique(x,x+tot)-x;
for(i=tot-;i>;i--)
{
if(x[i]-x[i-]>) x[tot++]=x[i-]+;
}
sort(x,x+tot);
build(,tot-,);
for(i=;i<n;i++)
{
int l=lower_bound(x,x+tot,p[i].l)-x;
int r=lower_bound(x,x+tot,p[i].r)-x;
update(,tot-,,l,r,i);
}
query(,tot-,);
cout<<ans<<endl;
}
return ;
}
原来搓代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 20005struct tree
{
int l,r;
}p[N<<];
struct node
{
int val,id,pos;
}h[N<<];int ans;
int color[N<<];
bool flag[N<<];
int change[N<<];bool cmp(node a,node b)
{
return a.val<b.val;
}
void pushup(int rt)
{
color[rt]=;
}
void pushdown(int rt)
{
if(change[rt]!=-)
{
change[rt<<]=change[rt<<|]=change[rt];
color[rt<<]=color[rt<<|]=change[rt];
change[rt]=-;
}
}
void build(int l,int r,int rt)
{
color[rt]=;
change[rt]=-;//初始化
if(l==r) return;
int m=(l+r)>>;
build(l,m,rt<<);
build(m+,r,rt<<|);
}
void update(int l,int r,int rt,int L,int R,int c)
{
if(l==L && R==r)
{
color[rt]=c;
change[rt]=c;
return;
}
pushdown(rt);
int m=(l+r)>>;
if(R<=m)
update(l,m,rt<<,L,R,c);
else if(L>m)
update(m+,r,rt<<|,L,R,c);
else
{
update(l,m,rt<<,L,m,c);
update(m+,r,rt<<|,m+,R,c);
}
pushup(rt);
}
void query(int l,int r,int rt)
{
int m=(l+r)>>;
if(color[rt])
{
if(!flag[color[rt]])
{
ans++;
flag[color[rt]]=;
}
return;
}
if(l==r) return; //忘了加这一句、一直RE
query(l,m,rt<<);
query(m+,r,rt<<|);
}
int main()
{
int n,i;
while(scanf("%d",&n)!=EOF)
{
ans=;
memset(flag,,sizeof(flag));
for(i=;i<n;i++)
{
scanf("%d%d",&p[i].l,&p[i].r);
h[i*].val=p[i].l;
h[i*].id=i;
h[i*].pos=;
h[i*+].val=p[i].r;
h[i*+].id=i;
h[i*+].pos=;
}
/* 离散化 */
sort(h,h+n*,cmp);
int last=-,total=;
for(i=;i<n*;i++)
{
if(h[i].val!=last)
{
total++;
if(i && h[i].val-h[i-].val>) total++; //注意这里、= =、手动插点
last=h[i].val;
}
if(h[i].val!=total)
{
if(h[i].pos) p[h[i].id].r=total;
else p[h[i].id].l=total;
}
}
build(,total,);
for(i=;i<n;i++)
{
update(,total,,p[i].l,p[i].r,i+);
}
query(,total,);
cout<<ans<<endl;
}
return ;
}
