[HDU5714]拍照
题目大意：
河上有\(n(n\le10^4)\)个船只，小明希望把尽可能多的船只都完整地拍到一张照片中。
小明位于河的边上，并且可以在河边的任意位置进行拍照，照相机的视野恰好为\(90\)度角，只能以垂直于河边的方向进行拍照。河上的船只全都可看作是平行于河边的一条线段，左右坐标分别为\(x_i,y_i\)，跟河边的距离为\(z_i\)，有的正在向左移动，有的正在向右移动，但移动速度恰好都是一样的。小明可以等待恰当的时间让尽量多的船只都走进照相机的视野里，你不需要考虑船只之间会互相遮挡视野的情况。
思路：
根据运动的相对性，我们不妨以向右移动的船作为参照物，那么剩下的船按照相同的速度像左运动。
显然\(y_i-x_i>2z_i\)的船注定无法完全拍摄。否则初始状态下，每个船在岸上可以被看见的区间是\([y_i-z_i,x_i+z_i]\)。
用对于向左、右行驶的船只，用线段树分别维护能够看到的区间。
枚举人站的位置\(i\)，由于向右行驶的船不动，能看到的向右行驶的船的数量是确定的。我们在向左行驶的线段树上查找大于等于\(i\)的位置上能看到的船数的最大值即可。
源代码：
#include#include #include inline int getint() { register char ch; register bool neg=false; while(!isdigit(ch=getchar())) neg|=ch=='-'; register int x=ch^'0'; while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0'); return neg?-x:x;}const int N=1e4+1;struct Boat { int x,y,z,d;};Boat b[N];int tmp[N<<1];class SegmentTree { #define _left <<1 #define _right <<1|1 #define mid ((b+e)>>1) private: int val[N<<3],tag[N<<3]; void push_up(const int &p) { val[p]=std::max(val[p _left],val[p _right]); } void push_down(const int &p) { if(tag[p]==0) return; tag[p _left]+=tag[p]; tag[p _right]+=tag[p]; val[p _left]+=tag[p]; val[p _right]+=tag[p]; tag[p]=0; } public: void build(const int &p,const int &b,const int &e) { tag[p]=val[p]=0; if(b==e) return; build(p _left,b,mid); build(p _right,mid+1,e); } void modify(const int &p,const int &b,const int &e,const int &l,const int &r) { if(b==l&&e==r) { val[p]++; tag[p]++; return; } push_down(p); if(l<=mid) modify(p _left,b,mid,l,std::min(mid,r)); if(r>mid) modify(p _right,mid+1,e,std::max(mid+1,l),r); push_up(p); } int query(const int &p,const int &b,const int &e,const int &l,const int &r) { if(b==l&&e==r) return val[p]; push_down(p); int ret=0; if(l<=mid) ret=std::max(ret,query(p _left,b,mid,l,std::min(mid,r))); if(r>mid) ret=std::max(ret,query(p _right,mid+1,e,std::max(mid+1,l),r)); return ret; } #undef _left #undef _right #undef mid};SegmentTree t[2];int main() { const int T=getint(); for(register int i=1;i<=T;i++) { int n=getint(); tmp[0]=0; for(register int i=1;i<=n;i++) { const int x=getint(),y=getint(),z=getint(),d=getint(); if(y-x>z*2) { i--; n--; continue; } b[i]=(Boat){x,y,z,d}; tmp[++tmp[0]]=x+z; tmp[++tmp[0]]=y-x; } std::sort(&tmp[1],&tmp[tmp[0]]+1); tmp[0]=std::unique(&tmp[1],&tmp[tmp[0]]+1)-&tmp[1]; t[0].build(1,1,tmp[0]); t[1].build(1,1,tmp[0]); for(register int i=1;i<=n;i++) { const int &x=b[i].x,&y=b[i].y,&z=b[i].z,&d=b[i].d; const int l=std::lower_bound(&tmp[1],&tmp[tmp[0]]+1,y-z)-tmp; const int r=std::lower_bound(&tmp[1],&tmp[tmp[0]]+1,x+z)-tmp; t[d==1].modify(1,1,tmp[0],l,r); } int ans=0; for(register int i=1;i<=tmp[0];i++) { ans=std::max(ans,t[1].query(1,1,tmp[0],1,i)+t[0].query(1,1,tmp[0],i,tmp[0])); } printf("Case #%d:\n%d\n",i,ans); } return 0;}