广告：
#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]被覆盖了
所以离散化时的取值略加修改。
WA：if(i==1||lsh[i].x!=lsh[i⑴].x)m++;
AC ：if(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;
}波比源码 – 精品源码模版分享 | www.bobi11.com
1. 本站所有资源来源于用户上传和网络，如有侵权请邮件联系站长！
2. 分享目的仅供大家学习和交流，您必须在下载后24小时内删除！
3. 不得使用于非法商业用途，不得违反国家法律。否则后果自负！
4. 本站提供的源码、模板、插件等等其他资源，都不包含技术服务请大家谅解！
5. 如有链接无法下载、失效或广告，请联系管理员处理！
6. 本站资源售价只是赞助，收取费用仅维持本站的日常运营所需！
7. 本站源码并不保证全部能正常使用，仅供有技术基础的人学习研究，请谨慎下载
8. 如遇到加密压缩包，请使用WINRAR解压,如遇到无法解压的请联系管理员！
波比源码 » 【BZOJ3888】【Usaco2015 Jan】Stampede 线段树判区间覆盖
波比源码 » 【BZOJ3888】【Usaco2015 Jan】Stampede 线段树判区间覆盖
