题解 P2667 【[TJOI2012]防御】

· · 题解

下面的题解管理员可以删了，改题了。

如果对于盾没爆前或者盾都是0的情况，一个线段树就可以了

现在问题是盾可以挡多少伤害（样例中2号1的盾可以挡2伤害）

这个可以直接在线段树上向下搜，因为每个叶子节点最多只会盾爆一次，所以效率是O(nlgn)的

具体操作是维护min，修改的时候区间减（需要lazy），每次找会爆盾的子树，爆盾的min改为maxint就好了

查询就是查路径上的伤害总和*2-盾挡的伤害或者伤害总和（盾没爆）

维护sum，不用下放（不用lazy），查询的时候统计即可

#include<cstdio>
using namespace std;
#define fo(a,b,c) for(int a=b;a<=c;a++)
#define LL long long
int read(){
    int a=0,f=0;char c=getchar();
    for(;c<'0'||c>'9';c=getchar())if(c=='-')f=1;
    for(;c>='0'&&c<='9';c=getchar())a=a*10+c-'0';
    return f?-a:a;
}
int min(int a,int b){return a<b?a:b;}
const int N=1e5+1,mo=1e9+9;//模数是1e9+9不是1e9+7
LL sum[N<<2],lazy[N<<2],boom[N],d[N],minx[N<<2];
void pushup(int rt){
    minx[rt]=min(minx[rt<<1],minx[rt<<1^1]);
}
void pushdown(int rt){
    if(minx[rt<<1]!=2e9)minx[rt<<1]-=lazy[rt];
    if(minx[rt<<1^1]!=2e9)minx[rt<<1^1]-=lazy[rt];
    lazy[rt<<1]+=lazy[rt],lazy[rt<<1^1]+=lazy[rt];
    lazy[rt]=0;
}
void build(int l,int r,int rt){
    if(l==r){
        d[l]=read(); 
        minx[rt]=d[l]?d[l]:2e9;
        return;
    }
    int m=l+r>>1;
    build(l,m,rt<<1);
    build(m+1,r,rt<<1^1);
    pushup(rt);
}
void change(int l,int r,int rt,int s){//除了这个函数都是线段树的函数，这个函数就是搜爆盾的函数
    if(l==r){d[l]=d[l]-minx[rt]+s;minx[rt]=2e9;boom[l]=1;return;}//记录盾挡的伤害和爆炸标记
    int m=l+r>>1;
    if(lazy[rt])pushdown(rt);
    if(s>=minx[rt<<1])change(l,m,rt<<1,s);
    if(s>=minx[rt<<1^1])change(m+1,r,rt<<1^1,s);
    pushup(rt);
}
void add(int l,int r,int rt,int L,int R,int c,LL s){
    if(L<=l&&r<=R){
        sum[rt]+=c;
        if(minx[rt]<=c)change(l,r,rt,c);
        if(minx[rt]!=2e9)minx[rt]-=c,lazy[rt]+=c;
        return;
    }
    s+=sum[rt];
    if(lazy[rt])pushdown(rt);
    int m=l+r>>1;
    if(L<=m)add(l,m,rt<<1,L,R,c,s);
    if(m<R)add(m+1,r,rt<<1^1,L,R,c,s);
    pushup(rt);
}
int query(int l,int r,int rt,int p){
    if(l==r)return sum[rt]%mo;
    int m=l+r>>1;
    if(p<=m)return(sum[rt]+query(l,m,rt<<1,p))%mo;
    else return(sum[rt]+query(m+1,r,rt<<1^1,p))%mo; 
}
int main(){
    int n=read(),q=read();LL ans=0;
    build(1,n,1);
    fo(i,1,q){
        scanf("\n");
        if(getchar()=='A'){
            int L=read(),R=read(),c=read();
            add(1,n,1,L,R,c,0);
        }
        else{
            int x=read();
            if(boom[x])ans=(ans+query(1,n,1,x)*2-d[x]+mo)%mo;
            else ans=(ans+query(1,n,1,x))%mo; 
        }
    }
    printf("%lld",ans);
    return 0;
}