线段树：
#include<iostream>
using namespace std;
int N,Len;
struct arr{
int x,y,c;
};
struct Node{
int a,b;
int cover;
}tree[600000];
arr a[5101],b[10010],c[5101];
int hash[10010];
arr ans[10010];
int cmp(const void* no1,const void* no2){
arr *nox=(arr*)no1,*noy=(arr*)no2;
return nox->x - noy->x;
}
void build(int Num,int la,int lb){
tree[Num].a=la;
tree[Num].b=lb;
tree[Num].cover=2;
if(la<lb){
int mid=(la+lb)>>1;
build(Num<<1,la,mid);
build((Num<<1)+1,mid+1,lb);
}
}
void insert(int Num,int la,int lb,int col){
if(tree[Num].a==la&&tree[Num].b==lb){
tree[Num].cover=col;
return;
}
int lc=Num<<1,rc=(Num<<1)+1;
if(tree[Num].cover>0){
tree[lc].cover=tree[Num].cover;
tree[rc].cover=tree[Num].cover;
}
tree[Num].cover=-1;
int mid=(tree[Num].a+tree[Num].b)>>1;
if(lb<=mid) insert(lc,la,lb,col);
else if(la>mid) insert(rc,la,lb,col);
else{
insert(lc,la,mid,col);
insert(rc,mid+1,lb,col);
}
}
int query(int Num,int la,int lb){
if(tree[Num].cover>0&&tree[Num].a<=la&&tree[Num].b>=lb)
return tree[Num].cover;
int mid=(tree[Num].a+tree[Num].b)>>1;
if(lb<=mid)
return query(Num<<1,la,lb);
else if(la>mid) return query((Num<<1)+1,la,lb);
}
int main()
{
scanf("%d",&N); getchar();
int lb=0;
char ch;
b[0].x=-1;
a[0].x=0; a[0].y=1000000000; a[0].c=c[0].c=2;
lb++; b[lb].x=a[0].x; b[lb].y=0; b[lb].c=0;
lb++; b[lb].x=a[0].y; b[lb].y=0; b[lb].c=1;
for(int i=1;i<=N;++i){
scanf("%d%d%c%c",&a[i].x,&a[i].y,&ch,&ch); getchar();
if(ch=='b') a[i].c=1;
else a[i].c=2;
c[i].c=a[i].c;
lb++; b[lb].x=a[i].x; b[lb].y=i; b[lb].c=0;
lb++; b[lb].x=a[i].y; b[lb].y=i; b[lb].c=1;
}
qsort(b+1,lb,sizeof(arr),cmp);
Len=0;
memset(hash,0,sizeof(hash));
for(int i=1;i<=lb;++i){
if(b[i].x!=b[i-1].x) Len++;
if(b[i].c)
c[b[i].y].y=Len;
else
c[b[i].y].x=Len;
hash[Len]=b[i].x;
}
build(1,1,Len-1);
for(int i=1;i<=N;++i)
insert(1,c[i].x,c[i].y-1,c[i].c);
for(int i=1;i<Len;++i){
ans[i].c=query(1,i,i);
ans[i].x=i;
ans[i].y=i+1;
}
ans[Len].x=Len-1; ans[Len].y=Len; ans[Len].c=2;
int ax,ay,ac,bx,by,bc,col;
ax=ay=ac=0;
int k;
for(k=1;k<=Len;++k)
if(ans[k].c==2){
bx=ans[k].x;
by=ans[k].y;
bc=hash[ans[k].y]-hash[ans[k].x]+1;
col=2;
break;
}
for(k++;k<=Len;++k)
if(ans[k].c==1){
if(ac<bc){
ax=bx; ay=by; ac=bc;
}
bc=0; col=1;
}
else{
if(col==1){
bx=ans[k].x; by=ans[k].y;
bc=hash[ans[k].y]-hash[ans[k].x]+1;
col=2;
}
else{
by=ans[k].y;
bc=hash[by]-hash[bx]+1;
}
}
if(ac<bc){
ax=bx; ay=by; ac=bc;
}
printf("%d %d\n",hash[ax],hash[ay]);
return 0;
}
线段切割：
#include<iostream>
using namespace std;
int N;
struct arr{
int x,y,c;
}a[5001],ans[1500001];
int tot;
void cut(int h,int t,int cur){
while(cur<=N&&(a[cur].x>=t||a[cur].y<=h)) cur++;
if(cur>N){
tot++;
ans[tot].x=h; ans[tot].y=t; ans[tot].c=t-h+1;
return;
}
if(h<a[cur].x&&t>a[cur].x)
cut(h,a[cur].x,cur+1);
if(h<a[cur].y&&t>a[cur].y)
cut(a[cur].y,t,cur+1);
}
int cmp(const void* no1,const void*no2){
arr *nox=(arr*)no1,*noy=(arr*)no2;
if(nox->x!=noy->x) return nox->x-noy->x;
else return nox->y-noy->y;
}
int main()
{
char s[2];
a[0].x=0; a[0].y=1000000000; a[0].c=1;
scanf("%d",&N);
for(int i=1;i<=N;++i){
scanf("%d%d%s",&a[i].x,&a[i].y,s);
if(s[0]=='b') a[i].c=0;
else a[i].c=1;
}
tot=0;
for(int i=0;i<=N;++i)
if(a[i].c)
cut(a[i].x,a[i].y,i+1);
qsort(ans+1,tot,sizeof(arr),cmp);
int ax,ay,ac,bx,by,bc;
ax=bx=ans[1].x;
ay=by=ans[1].y;
ac=bc=ans[1].c;
for(int i=2;i<=tot;++i)
if(by<ans[i].x){
if(ac<bc){
ax=bx; ay=by; ac=bc;
}
bx=ans[i].x; by=ans[i].y; bc=ans[i].c;
}
else if(by==ans[i].x){
by=ans[i].y;
bc=by-bx+1;
}
if(ac<bc){
ax=bx; ay=by; ac=bc;
}
printf("%d %d\n",ax,ay);
return 0;
}
posted on 2009-05-28 08:42
xfstart07 阅读(162)
评论(0) 编辑 收藏 引用 所属分类:
代码库