bird | Hexo

归档于 2019-10-26 06:32

这个题其实挺好的(除了条件没给清)

题解

最显然的dp,f[i]表示在i打了一枪最多得到多少只鸟,$f[i]=\sum\limits_{j=1}^{j<=i-k}f[j]+cnt[i]$然而如果一只鸟长度跨越几次开枪一只鸟会被重复算很多次,比如1秒开次枪,鸟100000长度,会多算

所以实际dp应该是$f[i]=\sum\limits_{j=1}^{j<=i-k} f[j]+cnt[i]-chongfu$,

可以利用差分思想,假设一只鸟覆盖[l,r],在鸟来之前[l,r]-1鸟走之后[l,r]+1,每多算一次[l,r]区间的鸟,也会被多减一次1,最后统一给[l,r]+1就得到了实际的值!

用线段树维护区间+,-,区间max,set维护每只鸟即可

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define A 2001101
struct tree{
    ll l,r,maxx,f;
}tr[A];
struct node{
    ll l,r;
    node(){}
    node(const ll &a,const ll &b){
        l=a,r=b;
    }
    friend bool operator < (const node &a,const node &b){
        return a.r<b.r;
    }
}qujian[A];
ll cmp(const node &a,const node &b){
    return a.l<b.l;
}
multiset<node> st;
multiset<node> :: iterator it;
ll maxx,tot,k,n,mx,ans;
ll cnt[A],in[A],f[A];
void built(ll x,ll l,ll r){
    tr[x].l=l,tr[x].r=r;
    if(l==r){
        return ;
    }
    ll mid=(tr[x].l+tr[x].r)>>1;
    built(x<<1,l,mid);
    built(x<<1|1,mid+1,r);
}
void up(ll x){
    tr[x].maxx=max(tr[x<<1].maxx,tr[x<<1|1].maxx);
}
void down(ll x){
    tr[x<<1].maxx+=tr[x].f;
    tr[x<<1|1].maxx+=tr[x].f;
    tr[x<<1].f+=tr[x].f;
    tr[x<<1|1].f+=tr[x].f;
    tr[x].f=0;
}
void seg_add(ll x,ll l,ll r,ll d){
//    printf("l=%lld r=%lld tr[x].l=%lld .r=%lld\n",l,r,tr[x].l,tr[x].r);
    if(tr[x].l>=l&&tr[x].r<=r){
        tr[x].maxx+=d;
        tr[x].f+=d;
        return ;
    }
    if(tr[x].f) down(x);
    ll mid=(tr[x].l+tr[x].r)>>1;
    if(mid>=l) seg_add(x<<1,l,r,d);
    if(mid<r) seg_add(x<<1|1,l,r,d);
    up(x);
}
void seg_max(ll x,ll l,ll r){
    if(l>r) return ;
//    printf("tr[x].l=%lld r=%lld l=%lld r=%lld\n",tr[x].l,tr[x].r,l,r);
    if(tr[x].l>=l&&tr[x].r<=r){
        maxx=max(maxx,tr[x].maxx);
        return ;
    }
    if(tr[x].f) down(x);
    ll mid=(tr[x].l+tr[x].r)>>1;
    if(mid>=l) seg_max(x<<1,l,r);
    if(mid<r) seg_max(x<<1|1,l,r);
    up(x);
}
void insert(ll x,ll pla,ll val){
//    printf("***l=%lld r=%lld pla=%lld val=%lld\n",tr[x].l,tr[x].r,pla,val);
    if(tr[x].l==tr[x].r){
        tr[x].maxx+=val;
        return ;
    }
    if(tr[x].f) down(x);
    ll mid=(tr[x].l+tr[x].r)>>1;
    if(mid>=pla) insert(x<<1,pla,val);
    else insert(x<<1|1,pla,val);
    up(x);
}
void print(ll x){
    printf("l=%lld r=%lld f=%lld maxx=%lld\n",tr[x].l,tr[x].r,tr[x].f,tr[x].maxx);
    if(tr[x].l==tr[x].r) return ;
    print(x<<1),print(x<<1|1);
}
int main(){
//    freopen("da.in","r",stdin);
//    freopen("ans.sol","w",stdout);
    scanf("%lld%lld",&n,&k);
    for(ll i=1;i<=n;i++){
        ll l,r;
        scanf("%lld%lld",&l,&r);
        if(r<0) continue ;
        l=max(0ll,l);
        qujian[++tot]=node(l,r);
        mx=max(mx,r);
        cnt[l]++,cnt[r+1]--;
        in[l]++;
    }
    for(ll i=1;i<=mx;i++)
        cnt[i]+=cnt[i-1];
    built(1,0,mx);
    sort(qujian+1,qujian+tot+1,cmp);
    ll ita=1,now=0;
    for(ll i=0;i<=mx;i++){
//        printf("i=%lld\n",i);
        while(qujian[ita].l==i){
            st.insert(qujian[ita]);
            ita++;now++;
        }
        maxx=0;
        seg_max(1,0,i-k);
        maxx+=cnt[i];
        ans=max(ans,maxx);
//        printf("***maxn=%lld\n",maxx);
        insert(1,i,maxx-now);
        it=st.lower_bound(node(0,0));
        while(it!=st.end()&&it->r<=i){
            ll l=it->l,r=it->r;
            node tmp=*it;
            seg_add(1,l,r,1);
            it++;
            now--;
            st.erase(tmp);
        }
//        print(1);
    }
    printf("%lld\n",ans);
}

View Code