您當(dāng)前位置：首頁(yè) > php開(kāi)源 > php教程 > 【BZOJ3888】【Usaco2015 Jan】Stampede 線(xiàn)段樹(shù)判區(qū)間覆蓋

【BZOJ3888】【Usaco2015 Jan】Stampede 線(xiàn)段樹(shù)判區(qū)間覆蓋

來(lái)源：程序員人生發(fā)布時(shí)間：2015-03-11 07:59:04 閱讀次數(shù)：2584次

題意：

$PoPoQQQ$ 站在原點(diǎn)上向y軸正半軸看，然后有1群羊駝從他眼前飛過(guò)。這些羊駝初始都在第2象限，尾巴在(Xi,Yi)，頭在(Xi+1,Yi)，每Ci秒向右走1個(gè)單位。
$PoPoQQQ$ 能看見(jiàn)1匹羊駝當(dāng)且僅當(dāng)它身體任意某部位x坐標(biāo)為0時(shí)，沒(méi)有其它y坐標(biāo)小于此羊駝的羊駝身體某部位x坐標(biāo)為0。
問(wèn) $PoPoQQQ$ 能看見(jiàn)幾匹羊駝？

題解：

離散化1下看每頭羊駝?dòng)庠統(tǒng)軸的時(shí)間左端點(diǎn)、右端點(diǎn)。
然后按y坐標(biāo)排序后挨個(gè)去線(xiàn)段樹(shù)里掃看是不是被完全覆蓋。

注意：

[3,4]和[4,5]被覆蓋不代表[4]被覆蓋了
所以離散化時(shí)的取值略加修改。
$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;
}