校门外的树 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
样例输出
2
1
线段树可解
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; #define N 40005 struct tree { int l,r; }p[N<<2]; int tot; int ans; int x[N]; int lazy[N<<2]; bool flag[N<<2]; void pushdown(int rt) { if(lazy[rt]!=-1) { lazy[rt<<1]=lazy[rt<<1|1]=lazy[rt]; lazy[rt]=-1; } } void build(int l,int r,int rt) { lazy[rt]=-1; if(l==r) return; int m=(l+r)>>1; build(l,m,rt<<1); build(m+1,r,rt<<1|1); } 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)>>1; if(R<=m) update(l,m,rt<<1,L,R,c); else if(L>m) update(m+1,r,rt<<1|1,L,R,c); else { update(l,m,rt<<1,L,m,c); update(m+1,r,rt<<1|1,m+1,R,c); } } void query(int l,int r,int rt) { if(lazy[rt]!=-1) { if(!flag[lazy[rt]]) { ans++; flag[lazy[rt]]=1; } return; } if(l>=r) return; pushdown(rt); int m=(l+r)>>1; query(l,m,rt<<1); query(m+1,r,rt<<1|1); } int main() { int n,i; while(scanf("%d",&n)!=EOF) { ans=0; tot=0; memset(flag,0,sizeof(flag)); for(i=0;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-1;i>0;i--) { if(x[i]-x[i-1]>1) x[tot++]=x[i-1]+1; } sort(x,x+tot); build(0,tot-1,1); for(i=0;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(0,tot-1,1,l,r,i); } query(0,tot-1,1); cout<<ans<<endl; } return 0; }
原来搓代码
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; #define N 20005 struct tree { int l,r; }p[N<<2]; struct node { int val,id,pos; }h[N<<2]; int ans; int color[N<<2]; bool flag[N<<2]; int change[N<<2]; bool cmp(node a,node b) { return a.val<b.val; } void pushup(int rt) { color[rt]=0; } void pushdown(int rt) { if(change[rt]!=-1) { change[rt<<1]=change[rt<<1|1]=change[rt]; color[rt<<1]=color[rt<<1|1]=change[rt]; change[rt]=-1; } } void build(int l,int r,int rt) { color[rt]=0; change[rt]=-1;//初始化 if(l==r) return; int m=(l+r)>>1; build(l,m,rt<<1); build(m+1,r,rt<<1|1); } 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)>>1; if(R<=m) update(l,m,rt<<1,L,R,c); else if(L>m) update(m+1,r,rt<<1|1,L,R,c); else { update(l,m,rt<<1,L,m,c); update(m+1,r,rt<<1|1,m+1,R,c); } pushup(rt); } void query(int l,int r,int rt) { int m=(l+r)>>1; if(color[rt]) { if(!flag[color[rt]]) { ans++; flag[color[rt]]=1; } return; } if(l==r) return; //忘了加这一句、一直RE query(l,m,rt<<1); query(m+1,r,rt<<1|1); } int main() { int n,i; while(scanf("%d",&n)!=EOF) { ans=0; memset(flag,0,sizeof(flag)); for(i=0;i<n;i++) { scanf("%d%d",&p[i].l,&p[i].r); h[i*2].val=p[i].l; h[i*2].id=i; h[i*2].pos=0; h[i*2+1].val=p[i].r; h[i*2+1].id=i; h[i*2+1].pos=1; } /* 离散化 */ sort(h,h+n*2,cmp); int last=-1,total=0; for(i=0;i<n*2;i++) { if(h[i].val!=last) { total++; if(i && h[i].val-h[i-1].val>1) 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(1,total,1); for(i=0;i<n;i++) { update(1,total,1,p[i].l,p[i].r,i+1); } query(1,total,1); cout<<ans<<endl; } return 0; }