您当前位置：首页 > php开源 > php教程 > 【BZOJ3888】【Usaco2015 Jan】Stampede 线段树判区间覆盖

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

来源：程序员人生发布时间：2015-03-11 07:59:04 阅读次数：2423次

题意：

$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;
}