程序员人生 网站导航

【BZOJ3888】【Usaco2015 Jan】Stampede 线段树判区间覆盖

栏目:php教程时间:2015-03-11 07:59:04

广告:

#include <stdio.h> int main() { puts("转载请注明出处[vmurder]谢谢"); puts("网址:blog.csdn.net/vmurder/article/details/44066313"); }

题意:

PoPoQQQ站在原点上向y轴正半轴看,然后有1群羊驼从他眼前飞过。这些羊驼初始都在第2象限,尾巴在(Xi,Yi),头在(Xi+1,Yi),每Ci秒向右走1个单位。
PoPoQQQ能看见1匹羊驼当且仅当它身体任意某部位x坐标为0时,没有其它y坐标小于此羊驼的羊驼身体某部位x坐标为0。
PoPoQQQ能看见几匹羊驼?

题解:

离散化1下看每头羊驼逾越y轴的时间左端点、右端点。
然后按y坐标排序后挨个去线段树里扫看是不是被完全覆盖。

注意:

[3,4]和[4,5]被覆盖不代表[4]被覆盖了
所以离散化时的取值略加修改。
WAif(i==1||lsh[i].x!=lsh[i⑴].x)m++;
ACif(i==1||lsh[i].x!=lsh[i⑴].x)m+=2;

代码:

#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define N 50500 #define ls (note<<1) #define rs (note<<1|1) using namespace std; struct LSH { long long l,r,x; bool operator < (const LSH &a)const{return x<a.x;} LSH(long long _l=0,long long _r=0,long long _x=0):l(_l),r(_r),x(_x){} }lsh[N*2],q[N]; int n,m,cnt; struct Segment_Tree { int l,r,c; }s[N*6*4]; void pushup(int note) { s[note].c=s[note].c|(s[ls].c&s[rs].c); } void build(int note,int l,int r) { s[note].l=l,s[note].r=r; if(l==r)return ; int mid=l+r>>1; build(ls,l,mid),build(rs,mid+1,r); } int cover(int note,int l,int r) { if(s[note].c)return 0; if(s[note].l==l&&r==s[note].r) { s[note].c=1; return 1; } int mid=s[note].l+s[note].r>>1,ret; if(r<=mid)ret=cover(ls,l,r); else if(l>mid)ret=cover(rs,l,r); else ret=(cover(ls,l,mid)|cover(rs,mid+1,r)); pushup(note); return ret; } int main() { freopen("test.in","r",stdin); int i,j,k; long long a,b,c; scanf("%d",&n); for(i=1;i<=n;i++) { cin>>a>>b>>c; q[i].x=b,a=(-a-1)*c,c+=a; lsh[++cnt]=LSH(i,0,a); lsh[++cnt]=LSH(i,1,c); } sort(lsh+1,lsh+cnt+1); for(i=1;i<=cnt;i++) { if(i==1||lsh[i].x!=lsh[i-1].x)m+=2; if(lsh[i].r==0)q[lsh[i].l].l=m; else q[lsh[i].l].r=m; } sort(q+1,q+n+1); build(1,1,m); int ans=0; for(i=1;i<=n;i++) { ans+=cover(1,q[i].l,q[i].r); } printf("%d ",ans); return 0; }
------分隔线----------------------------
------分隔线----------------------------

最新技术推荐