[noip模拟赛]bird

https://www.zybuluo.com/ysner/note/1295414

题面

$R$是一个猎人,他准备打猎,他站在平面直角坐标系的$(0,0)$位置。

天上有$n$只小鸟从右往左以$1m/s$的速度水平飞过,每只小鸟都是一条水平方向的线段。

由于$R$枪法不太好,他只会竖直向上开枪,此时与$y$轴有交(包括端点)的小鸟都会被击中并成为$R$的猎物。

$R$在开完一枪后需要$k$秒来装弹,在此期间不能再次开枪。

你需要求出$R$最多能得到多少只猎物。

$n\leq10^5,\max\{|l|,|r|\}\leq5*10^5$

解析

很容易能想到一个$DP$方程式：

设$f_i$表示当时间进行到时刻$i$，并且这时打一枪，最多总共获得多少猎物。

设$s_i$表示在时间$i$打一枪能获得多少收益。

设$chongfu(i,j)$表示$s_i$与$f_j$中包含猎物的重复个数。

则$$f_i=\max_{j=0}^{i-k}{f_j-chongfu(i,j)}+s_i$$

看起来那个$chongfu(i,j)$相当难求，因为每转移一次，都要维护转移到$f_i$的猎物，还要去重，复杂度很危险。

其实不妨这么想，可以用差分$O(n)$求出所有$s_j$。同时出现在$j$、$i$的线段，就是在$j$中出现后，到$i$时没有被删除的线段。

我们可以在更新$f_j$的值时，在线段树上将其更新为：$f_j-$在时刻$j$出现的边，这样每当一条线段终结时，在线段树上给这条线段区间加一即可。

这样在到时刻$i$时，$f_j$的值就是$f_j-chongfu(i,j)$。

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<vector>

#include<set>

#define ll long long

#define re register

#define il inline

#define ls x<<1

#define rs x<<1|1

#define pb(a) push_back(a)

#define fp(i,a,b) for(re int i=a;i<=b;i++)

#define fq(i,a,b) for(re int i=a;i>=b;i--)

using namespace std;

const int N=5e5+100;

struct dat

{

  int l,r;

  il bool operator < (const dat &o) const

  {

    if(r==o.r) return l<o.l;

    return r<o.r;

  }

}a[N];

int n,m,k,tot,cha[N],in[N],mx,p=1,ans,now,t[N<<2],tag[N<<2],f[N];

il int gi()

{

  re int x=0,t=1;

  re char ch=getchar();

  while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();

  if(ch=='-') t=-1,ch=getchar();

  while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();

  return x*t;

}

il void upd(re int x){t[x]=max(t[ls],t[rs]);}

il void cover(re int x,re int w){t[x]+=w;tag[x]+=w;}

il void Pushdown(re int x){cover(ls,tag[x]);cover(rs,tag[x]);tag[x]=0;}

il void Modify(re int x,re int l,re int r,re int pos,re int w)

{

  if(l==r) {t[x]=w;return;}

  re int mid=l+r>>1;

  if(tag[x]) Pushdown(x);

  if(pos<=mid) Modify(ls,l,mid,pos,w);

  else Modify(rs,mid+1,r,pos,w);

  upd(x);

}

il void Modify(re int x,re int l,re int r,re int ql,re int qr,re int w)

{

  if(ql<=l&&r<=qr) {cover(x,w);return;}

  re int mid=l+r>>1;

  if(tag[x]) Pushdown(x);

  if(ql<=mid) Modify(ls,l,mid,ql,qr,w);

  if(qr>mid) Modify(rs,mid+1,r,ql,qr,w);

  upd(x);

}

il int Query(re int x,re int l,re int r,re int ql,re int qr)

{

  if(ql<=l&&r<=qr) return t[x];

  re int mid=l+r>>1;

  if(tag[x]) Pushdown(x);

  if(qr<=mid) return Query(ls,l,mid,ql,qr);

  if(ql>mid) return Query(rs,mid+1,r,ql,qr);

  return max(Query(ls,l,mid,ql,qr),Query(rs,mid+1,r,ql,qr));

}

int main()

{

  freopen("bird.in","r",stdin);

  freopen("bird.out","w",stdout);

  n=gi();k=gi();

  fp(i,1,n)

    {

      re int l=max(0,gi()),r=gi();

      if(r<0) continue;++l;++r;

      a[++tot]=(dat){l,r};

      ++cha[l];++in[l];--cha[r+1];mx=max(mx,r+1);

    }

  sort(a+1,a+1+tot);

  fp(i,1,mx) cha[i]+=cha[i-1];

  fp(i,1,mx)

    {

      f[i]=cha[i]+Query(1,0,mx,max(0,i-2*k),max(0,i-k));

      ans=max(ans,f[i]);now+=in[i];

      Modify(1,0,mx,i,f[i]-now);

      while(p<=tot&&a[p].r==i)

	{

	  --now;

	  Modify(1,0,mx,a[p].l,a[p].r,1);

	  ++p;

	}

    }

  printf("%d\n",ans);

  fclose(stdin);

  fclose(stdout);

  return 0;

}

巴特西

[noip模拟赛]bird

https://www.zybuluo.com/ysner/note/1295414

题面

解析

最新文章

热门文章