您當前位置：首頁 > php開源 > php教程 > 【BZOJ3888】【Usaco2015 Jan】Stampede 線段樹判區間覆蓋

【BZOJ3888】【Usaco2015 Jan】Stampede 線段樹判區間覆蓋

來源：程序員人生發布時間：2015-03-11 07:59:04 閱讀次數：2578次

題意：

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