[关闭]
@ysner 2018-09-27T19:36:42.000000Z 字数 2561 阅读 2236

[noip模拟赛]bird

线段树 DP 线段树优化DP 自治领


题面

是一个猎人,他准备打猎,他站在平面直角坐标系的位置。
天上有只小鸟从右往左以的速度水平飞过,每只小鸟都是一条水平方向的线段。
由于枪法不太好,他只会竖直向上开枪,此时与轴有交(包括端点)的小鸟都会被击中并成为的猎物。
在开完一枪后需要秒来装弹,在此期间不能再次开枪。
你需要求出最多能得到多少只猎物。

解析

很容易能想到一个方程式:
表示当时间进行到时刻,并且这时打一枪,最多总共获得多少猎物。
表示在时间打一枪能获得多少收益。
表示中包含猎物的重复个数。

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

其实不妨这么想,可以用差分求出所有。同时出现在的线段,就是在中出现后,到时没有被删除的线段。

我们可以在更新的值时,在线段树上将其更新为:出的边,这样每当一条线段终结时,在线段树上给这条线段区间加一即可。
这样在到时刻时,的值就是

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cstdlib>
  4. #include<cstring>
  5. #include<cmath>
  6. #include<algorithm>
  7. #include<vector>
  8. #include<set>
  9. #define ll long long
  10. #define re register
  11. #define il inline
  12. #define ls x<<1
  13. #define rs x<<1|1
  14. #define pb(a) push_back(a)
  15. #define fp(i,a,b) for(re int i=a;i<=b;i++)
  16. #define fq(i,a,b) for(re int i=a;i>=b;i--)
  17. using namespace std;
  18. const int N=5e5+100;
  19. struct dat
  20. {
  21. int l,r;
  22. il bool operator < (const dat &o) const
  23. {
  24. if(r==o.r) return l<o.l;
  25. return r<o.r;
  26. }
  27. }a[N];
  28. int n,m,k,tot,cha[N],in[N],mx,p=1,ans,now,t[N<<2],tag[N<<2],f[N];
  29. il int gi()
  30. {
  31. re int x=0,t=1;
  32. re char ch=getchar();
  33. while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
  34. if(ch=='-') t=-1,ch=getchar();
  35. while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  36. return x*t;
  37. }
  38. il void upd(re int x){t[x]=max(t[ls],t[rs]);}
  39. il void cover(re int x,re int w){t[x]+=w;tag[x]+=w;}
  40. il void Pushdown(re int x){cover(ls,tag[x]);cover(rs,tag[x]);tag[x]=0;}
  41. il void Modify(re int x,re int l,re int r,re int pos,re int w)
  42. {
  43. if(l==r) {t[x]=w;return;}
  44. re int mid=l+r>>1;
  45. if(tag[x]) Pushdown(x);
  46. if(pos<=mid) Modify(ls,l,mid,pos,w);
  47. else Modify(rs,mid+1,r,pos,w);
  48. upd(x);
  49. }
  50. il void Modify(re int x,re int l,re int r,re int ql,re int qr,re int w)
  51. {
  52. if(ql<=l&&r<=qr) {cover(x,w);return;}
  53. re int mid=l+r>>1;
  54. if(tag[x]) Pushdown(x);
  55. if(ql<=mid) Modify(ls,l,mid,ql,qr,w);
  56. if(qr>mid) Modify(rs,mid+1,r,ql,qr,w);
  57. upd(x);
  58. }
  59. il int Query(re int x,re int l,re int r,re int ql,re int qr)
  60. {
  61. if(ql<=l&&r<=qr) return t[x];
  62. re int mid=l+r>>1;
  63. if(tag[x]) Pushdown(x);
  64. if(qr<=mid) return Query(ls,l,mid,ql,qr);
  65. if(ql>mid) return Query(rs,mid+1,r,ql,qr);
  66. return max(Query(ls,l,mid,ql,qr),Query(rs,mid+1,r,ql,qr));
  67. }
  68. int main()
  69. {
  70. freopen("bird.in","r",stdin);
  71. freopen("bird.out","w",stdout);
  72. n=gi();k=gi();
  73. fp(i,1,n)
  74. {
  75. re int l=max(0,gi()),r=gi();
  76. if(r<0) continue;++l;++r;
  77. a[++tot]=(dat){l,r};
  78. ++cha[l];++in[l];--cha[r+1];mx=max(mx,r+1);
  79. }
  80. sort(a+1,a+1+tot);
  81. fp(i,1,mx) cha[i]+=cha[i-1];
  82. fp(i,1,mx)
  83. {
  84. f[i]=cha[i]+Query(1,0,mx,max(0,i-2*k),max(0,i-k));
  85. ans=max(ans,f[i]);now+=in[i];
  86. Modify(1,0,mx,i,f[i]-now);
  87. while(p<=tot&&a[p].r==i)
  88. {
  89. --now;
  90. Modify(1,0,mx,a[p].l,a[p].r,1);
  91. ++p;
  92. }
  93. }
  94. printf("%d\n",ans);
  95. fclose(stdin);
  96. fclose(stdout);
  97. return 0;
  98. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注