首页 > 代码库 > HDU 1199 && ZOJ 2301 线段树离散化
HDU 1199 && ZOJ 2301 线段树离散化
一段长度未知的线段,一种操作:a b c ,表示区间[a,b]涂为颜色C,w代表白色,b代表黑色,问最终的最长连续白色段,输出起始位置和终止位置
离散化处理,和平常的离散化不同,需要把点化成线段,左闭右开,即对于一段区间[a,b],转化成区间[a,b+1)
#include "stdio.h" #include "string.h" #include "algorithm" using namespace std; struct node { int l,r,x; }data[20010]; struct Mark { int l,r,op; }mark[20010]; struct B { int id,x,dir; }b[20010]; int color[20010]; bool cmp(B a,B b) { return a.x<b.x; } void build(int l,int r,int k) { int mid; if (l>=r) return ; data[k].l=l; data[k].r=r; data[k].x=0; if (l==r-1) return ; mid=(l+r)/2; build(l,mid,k*2); build(mid,r,k*2+1); } void updata(int l,int r,int k,int op) { int mid; if (l>=r) return ; if (data[k].l==l && data[k].r==r) { data[k].x=op; return ; } if (data[k].x!=-1 && data[k].x!=op) { data[k*2].x=data[k*2+1].x=data[k].x; data[k].x=-1; } mid=(data[k].l+data[k].r)/2; if (r<=mid) updata(l,r,k*2,op); else if (l>=mid) updata(l,r,k*2+1,op); else { updata(l,mid,k*2,op); updata(mid,r,k*2+1,op); } } void query(int k) { int i; if (data[k].l>=data[k].r) return ; if (data[k].x!=-1) { for (i=data[k].l;i<data[k].r;i++) color[i]=data[k].x; return ; } query(k*2); query(k*2+1); } int main() { int a[20010],n,cnt,m,ans,ans_l,ans_r,l,r,i; char ch; while (scanf("%d",&n)!=EOF) { cnt=0; for (i=1;i<=n;i++) { scanf("%d%d %c",&l,&r,&ch); if (ch=='w') mark[i].op=1; else mark[i].op=0; b[cnt].x=l; b[cnt].id=i; b[cnt++].dir=-1; b[cnt].x=r+1; b[cnt].id=i; b[cnt++].dir=1; } sort(b,b+cnt,cmp);// 离散化辅助数组 m=1; if(b[0].dir==-1) mark[b[0].id].l=1; else mark[b[0].id].r=1; a[1]=b[0].x; for (i=1;i<cnt;i++) { if (b[i].x!=b[i-1].x){ m++; a[m]=b[i].x;} // 将离散化之前的数从小到大存入a数组 if (b[i].dir==-1) mark[b[i].id].l=m; else mark[b[i].id].r=m; } build(1,m,1); memset(color,0,sizeof(color)); // 记录叶子节点颜色 for (i=1;i<=n;i++) updata(mark[i].l,mark[i].r,1,mark[i].op); query(1); ans=0; for (i=1;i<=m;i++) { if (color[i]!=1) continue; l=a[i]; while (color[i]==1) i++; r=a[i]; if (r-l>ans) { ans=r-l; ans_l=l; ans_r=r; } } if (ans==0) printf("Oh, my god\n"); else printf("%d %d\n",ans_l,ans_r-1); } return 0; }
HDU 1199 && ZOJ 2301 线段树离散化
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。