(\)
Description
有 (n) 人，第 (i) 个人有一个护甲值 (a_i)。
有 (m) 次操作，分为以下两种：
- (A l r x) 对编号在 ([l,r]) 内的人造成 (x) 点伤害。
- (Q p) 求第 (p) 个人当前受到的伤害值之和。
护甲值的作用是，如果当前总伤害未超过护甲值，只对这个人造成一倍伤害。
当总伤害第一次 (ge) 护甲值时护甲破了，以后 的攻击都造成二倍伤害，破甲时的攻击 只造成一倍伤害 。
- (n,mle 10^5,xle 10^4,a_ile 10^6)
(\)
Solution
我们记 (val_i) 表示第 (i) 个人被破甲时累积的伤害值是多少，答案就是第 (i) 个人受到的总伤害值 ( imes 2-val_i) 。
然后考虑如何求 (val_i) 。线段树 (DFS) 。
线段树维护当前节点收到的伤害之和，以及当前区间最小 剩余 护甲值。
每次攻击打 (lazy tag) ，同时判断区间最小值是否 (le 0) 。
如果出现最小值 (le 0) 的情况，就从当前节点 开始向下 (DFS) ， $pushdown $ 之后，分别判断左右子树，只要子树最小就继续 (DFS) 这个子树。到了叶节点就可以统计对应位置的 (val) 值了。
记得修改之后及时 (pushup) ，为了不影响后续的判断，我们把更新过的叶节点剩余护甲值设为 (inf)。
并不需要循环，因为每次攻击时左右子节点至多被 (DFS) 一次就可以处理掉所有不合法情况。
因为每个节点至多被(DFS) 进去一次，所以复杂度还是 (n log n) 的。
以及 (DFS) 之前要先判断最小值是否 (le 0)，否则可能会出现多次进叶节点的情况。
(\)
Code
#include<cmath>
#include<cstdio>
#include<cctype>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define N 100010
#define gc getchar
#define Rg register
#define mid ((l+r)>>1)
#define inf 1000000000
#define mod 1000000009
using namespace std;
inline int rd(){
int x=0; bool f=0; char c=gc();
while(!isdigit(c)){if(c=='-')f=1;c=gc();}
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc();}
return f?-x:x;
}
int n,m,lim[N],val[N];
struct segment{
int root,ptr;
inline int newnode(){return ++ptr;}
struct node{int ls,rs,mn,tag;}c[N<<1];
inline void pushup(int rt){
c[rt].mn=min(c[c[rt].ls].mn,c[c[rt].rs].mn);
}
inline void pushdown(int rt){
if(c[rt].tag){
c[c[rt].ls].tag+=c[rt].tag;
c[c[rt].ls].mn-=c[rt].tag;
c[c[rt].rs].tag+=c[rt].tag;
c[c[rt].rs].mn-=c[rt].tag;
c[rt].tag=0;
}
}
void build(int &rt,int l,int r){
rt=newnode();
if(l==r){
c[rt].mn=lim[l];
return;
}
build(c[rt].ls,l,mid);
build(c[rt].rs,mid+1,r);
pushup(rt);
}
void check(int rt,int l,int r){
if(l==r){
val[l]=lim[l]-c[rt].mn;
c[rt].mn=inf;
return;
}
pushdown(rt);
if(c[c[rt].ls].mn<=0) check(c[rt].ls,l,mid);
if(c[c[rt].rs].mn<=0) check(c[rt].rs,mid+1,r);
pushup(rt);
}
void updata(int rt,int l,int r,int L,int R,int w){
if(l>R||r<L) return;
if(l>=L&&r<=R){
c[rt].tag+=w;
c[rt].mn-=w;
if(c[rt].mn<=0) check(rt,l,r);
return;
}
pushdown(rt);
if(L<=mid) updata(c[rt].ls,l,mid,L,R,w);
if(R>mid) updata(c[rt].rs,mid+1,r,L,R,w);
pushup(rt);
}
int query(int rt,int l,int r,int p){
if(p>r||p<l) return 0;
if(l==r) return c[rt].tag;
pushdown(rt);
if(p<=mid) return query(c[rt].ls,l,mid,p)+c[rt].tag;
else return query(c[rt].rs,mid+1,r,p)+c[rt].tag;
}
}tree;
int res;
int main(){
n=rd(); m=rd();
for(Rg int i=1;i<=n;++i) lim[i]=rd();
tree.build(tree.root,1,n);
char c;
for(Rg int i=1,x,y,w;i<=m;++i){
c=gc(); while(!isalpha(c)) c=gc();
if(c=='Q'){
x=rd();
if(val[x]) (res+=(tree.query(tree.root,1,n,x)*2-val[x])%mod)%=mod;
else (res+=tree.query(tree.root,1,n,x)%mod)%=mod;
}
else{
x=rd(); y=rd(); w=rd();
tree.updata(tree.root,1,n,x,y,w);
}
}
printf("%d
",res);
return 0;
}