https://www.zybuluo.com/ysner/note/1332539
题面
解析
一道挺棒棒的线段树。
显然一次伤害到来时我们要先看看区间内哪些点的护甲没了。
这个可以通过维护区间最小值（维护护甲的剩余承受能力）来完成。
如果发现区间最小值小于等于当前伤害，就去暴力找出区间内护甲即将失效的点（\(change\))，进行单点修改，标记其已爆炸。
因为一个点护甲只会失效一次，所以总复杂度\(O(nlogn)\)。
注意下护甲失效后，剩余承受能力应置为\(inf\)。
我们也可以维护每个点受到伤害的攻击力总数，这个可以通过标记可持久化完成（详见数组\(s\)）。
但是我们不容易知道一个点受到的攻击力，有多少造成了一倍伤害，有多少造成了两倍伤害。
在护甲还在时，伤害\(=\)攻击力
在护甲即将不在时，我们可以算出护甲当前受到的所有伤害，这些都是一倍伤害，存在\(t\)里。
在护甲不再时，伤害\(=\)攻击力\(*2-t\)
#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#define ll long long
#define re register
#define il inline
#define ls x<<1
#define rs x<<1|1
#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=1e5+100,mod=1e9+9;
int n,q,t[N],mn[N<<2],tag[N<<2],s[N<<2],boom[N];
ll ans;
char op[10];
il ll gi()
{
re ll 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 ll min(re int x,re int y){return x<y?x:y;}
il void upd(re int x){mn[x]=min(mn[ls],mn[rs]);}
il void cover(re int x,re int w)
{
tag[x]+=w;
if(mn[x]!=2e9) mn[x]-=w;
}
il void Pushdown(re int x)
{
cover(ls,tag[x]);cover(rs,tag[x]);tag[x]=0;
}
il void Build(re int x,re int l,re int r)
{
if(l==r)
{
t[l]=gi();
mn[x]=t[l]>0?t[l]:2e9;
return;
}
re int mid=l+r>>1;
Build(ls,l,mid);Build(rs,mid+1,r);
upd(x);
}
il void Change(re int x,re int l,re int r,re int w)
{
if(l==r)
{
t[l]=t[l]-mn[x]+w;mn[x]=2e9;boom[l]=1;
return;
}
re int mid=l+r>>1;
if(tag[x]) Pushdown(x);
if(mn[ls]<=w) Change(ls,l,mid,w);
if(mn[rs]<=w) Change(rs,mid+1,r,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)
{
s[x]+=w;
if(mn[x]<=w) Change(x,l,r,w);
if(mn[x]!=2e9) mn[x]-=w,tag[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 pos)
{
if(l==r) return s[x];
re int mid=l+r>>1;
//if(tag[x]) Pushdown(x);
if(pos<=mid) return Query(ls,l,mid,pos)+s[x];
return Query(rs,mid+1,r,pos)+s[x];
}
int main()
{
n=gi();q=gi();
Build(1,1,n);
while(q--)
{
scanf("%s",op+1);
if(op[1]=='A')
{
re int l=gi(),r=gi(),w=gi();
Modify(1,1,n,l,r,w);
}
if(op[1]=='Q')
{
re int pos=gi();
if(boom[pos]) ans+=Query(1,1,n,pos)*2-t[pos];
else ans+=Query(1,1,n,pos);
}
}
printf("%lld\n",ans%mod);
return 0;
}