[关闭]
@ysner 2018-11-05T00:19:02.000000Z 字数 2162 阅读 2014

[TJOI2012]防御

线段树


题面

戳我

解析

一道挺棒棒的线段树。
显然一次伤害到来时我们要先看看区间内哪些点的护甲没了。
这个可以通过维护区间最小值(维护护甲的剩余承受能力)来完成。

如果发现区间最小值小于等于当前伤害,就去暴力找出区间内护甲即将失效的点(),进行单点修改,标记其已爆炸。
因为一个点护甲只会失效一次,所以总复杂度
注意下护甲失效后,剩余承受能力应置为

我们也可以维护每个点受到伤害的攻击力总数,这个可以通过标记可持久化完成(详见数组)。

但是我们不容易知道一个点受到的攻击力,有多少造成了一倍伤害,有多少造成了两倍伤害。
在护甲还在时,伤害攻击力
在护甲即将不在时,我们可以算出护甲当前受到的所有伤害,这些都是一倍伤害,存在里。
在护甲不再时,伤害攻击力

  1. #include<iostream>
  2. #include<cmath>
  3. #include<cstdio>
  4. #include<cstdlib>
  5. #include<cstring>
  6. #include<algorithm>
  7. #define ll long long
  8. #define re register
  9. #define il inline
  10. #define ls x<<1
  11. #define rs x<<1|1
  12. #define fp(i,a,b) for(re int i=a;i<=b;i++)
  13. #define fq(i,a,b) for(re int i=a;i>=b;i--)
  14. using namespace std;
  15. const int N=1e5+100,mod=1e9+9;
  16. int n,q,t[N],mn[N<<2],tag[N<<2],s[N<<2],boom[N];
  17. ll ans;
  18. char op[10];
  19. il ll gi()
  20. {
  21. re ll x=0,t=1;
  22. re char ch=getchar();
  23. while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
  24. if(ch=='-') t=-1,ch=getchar();
  25. while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  26. return x*t;
  27. }
  28. il ll min(re int x,re int y){return x<y?x:y;}
  29. il void upd(re int x){mn[x]=min(mn[ls],mn[rs]);}
  30. il void cover(re int x,re int w)
  31. {
  32. tag[x]+=w;
  33. if(mn[x]!=2e9) mn[x]-=w;
  34. }
  35. il void Pushdown(re int x)
  36. {
  37. cover(ls,tag[x]);cover(rs,tag[x]);tag[x]=0;
  38. }
  39. il void Build(re int x,re int l,re int r)
  40. {
  41. if(l==r)
  42. {
  43. t[l]=gi();
  44. mn[x]=t[l]>0?t[l]:2e9;
  45. return;
  46. }
  47. re int mid=l+r>>1;
  48. Build(ls,l,mid);Build(rs,mid+1,r);
  49. upd(x);
  50. }
  51. il void Change(re int x,re int l,re int r,re int w)
  52. {
  53. if(l==r)
  54. {
  55. t[l]=t[l]-mn[x]+w;mn[x]=2e9;boom[l]=1;
  56. return;
  57. }
  58. re int mid=l+r>>1;
  59. if(tag[x]) Pushdown(x);
  60. if(mn[ls]<=w) Change(ls,l,mid,w);
  61. if(mn[rs]<=w) Change(rs,mid+1,r,w);
  62. upd(x);
  63. }
  64. il void Modify(re int x,re int l,re int r,re int ql,re int qr,re int w)
  65. {
  66. if(ql<=l&&r<=qr)
  67. {
  68. s[x]+=w;
  69. if(mn[x]<=w) Change(x,l,r,w);
  70. if(mn[x]!=2e9) mn[x]-=w,tag[x]+=w;
  71. return;
  72. }
  73. re int mid=l+r>>1;
  74. if(tag[x]) Pushdown(x);
  75. if(ql<=mid) Modify(ls,l,mid,ql,qr,w);
  76. if(qr>mid) Modify(rs,mid+1,r,ql,qr,w);
  77. upd(x);
  78. }
  79. il int Query(re int x,re int l,re int r,re int pos)
  80. {
  81. if(l==r) return s[x];
  82. re int mid=l+r>>1;
  83. //if(tag[x]) Pushdown(x);
  84. if(pos<=mid) return Query(ls,l,mid,pos)+s[x];
  85. return Query(rs,mid+1,r,pos)+s[x];
  86. }
  87. int main()
  88. {
  89. n=gi();q=gi();
  90. Build(1,1,n);
  91. while(q--)
  92. {
  93. scanf("%s",op+1);
  94. if(op[1]=='A')
  95. {
  96. re int l=gi(),r=gi(),w=gi();
  97. Modify(1,1,n,l,r,w);
  98. }
  99. if(op[1]=='Q')
  100. {
  101. re int pos=gi();
  102. if(boom[pos]) ans+=Query(1,1,n,pos)*2-t[pos];
  103. else ans+=Query(1,1,n,pos);
  104. }
  105. }
  106. printf("%lld\n",ans%mod);
  107. return 0;
  108. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注