首页 > 代码库 > 线段树 [SWUST OJ 764] 校门外的树 Plus Plus
线段树 [SWUST OJ 764] 校门外的树 Plus Plus
校门外的树 Plus Plus(0764)
Time limit(ms): 1000 Memory limit(kb): 65535 Submission: 214 Accepted: 15
Description
西南某科技大学的校门外长度为 L 的公路上有一排树，每两棵相邻的树之间的间隔都是 1 米。我们可以把马路看成一个数轴，马路的一端在数轴 1 的位置，另一端在 L 的位置；数轴上的每个整数点，即 1，2，……，L，都种有一棵树。
现在要将这排树的某一段涂成某种颜色，给定 N 组区间[ J,K ]，表示从 J 到 K 的树都要涂上一种颜色（每次涂的颜色不一样,而且每次涂色会覆盖掉原来的颜色），区间之间可能有重叠的部分, L 的长度为 1000,0000。现在你的任务是计算涂色工作结束后，这一排树里总共有多少种颜色的树？（没涂过色的不算）
Input
第一行为一个整数N （1<=N<=10000）。 接下来的N行每行是两个整数数J，K（1<=J<=K<=1000,0000），表示涂色的起止区间。
多组测试数据。
Output
一个整数，表示有多少种颜色的树。Sample Input
2
1 10
5 5
1
1 1
Sample Output
2
1
Source
SWUST Monthly Contest - 2011.3.19, Chen.Yi
我觉得我有写一点东西的必要了、弱爆了啊、由于这道题的原题是其他OJ上的、在POJ上、由于它题目数据有问题、水过、、然后拿到NYOJ上去WA、由于是自己写的、心里始终有点不想改的意愿、百度、发现网上一部人代码是错的、另一部分是先排序去重、再离散、再二分、感觉好复杂、所以感觉不会再爱了、所以睡觉了、今早醒来再做、发现可以不用二分、做吧、各种RE、我以为是数组的原因、各种改、然后发现是我多输出了、把调试的也输出了、可是这不会RE啊、管他呢、先改了、我晕、改了就过了、不觉明历、好吧、现在回到SWUST OJ做、由于输入格式不一样、那边是T组数据、再输入n、这里是输入n到文件结束、然后脑残的一直错、后来发现了改了、然后又各种RE、这次没多输出啊、然后我觉得应该是数组大小的问题、然后别说了、RE到死、最后发现在query的时候没有加if(l==r) return; 改了A了。。。。。。心酸啊、弱渣、哎、泪啊 0.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;}
线段树 [SWUST OJ 764] 校门外的树 Plus Plus
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。