题解：P11217 【MX-S4-T1】「yyOI R2」youyou 的垃圾桶

许多 · 2024-10-20 19:27:13 · 题解

非常明显的一道线段树二分题。

每场战斗前的强化就相当于区间加操作。

我们先对整个区间进行整体操作，计算 youyou 被所有垃圾桶攻击一遍后剩余血量，并用 k 记录当前垃圾桶攻击力翻了多少倍。

当 youyou 的血量不足以支撑被全部垃圾桶攻击时，直接在线段树上二分，查找最多还能被攻击几次。

细节看代码。

CODE

#include<bits/stdc++.h>
#include<cstdio>
#define LL long long 
#define N 222222 
#define pushup(now) sum[now]=sum[now<<1]+sum[now<<1|1]
inline LL read(){
    LL x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x*f;
}
using namespace std;
LL n,q,W;
LL sum[N<<2],add[N<<2];
void build(LL l,LL r,LL now){
    if(l==r){
        sum[now]=read();
        return ;
    }
    LL mid=l+r>>1;
    build(l,mid,now<<1);build(mid+1,r,now<<1|1);
    pushup(now);
    return ;
}
void Add(LL l,LL r,LL now,LL v){
    sum[now]+=(r-l+1)*v;
    add[now]+=v;
    return ;
}
void pushdown(LL l,LL r,LL now){
    if(!add[now])return ;
    LL mid=l+r>>1;
    Add(l,mid,now<<1,add[now]);
    Add(mid+1,r,now<<1|1,add[now]);
    add[now]=0;
    return ;
}
void modify(LL l,LL r,LL now,LL x,LL y,LL v){
    if(l>=x&&r<=y)return Add(l,r,now,v);
    LL mid=l+r>>1;
    pushdown(l,r,now);
    if(x<=mid)modify(l,mid,now<<1,x,y,v);
    if(y>mid)modify(mid+1,r,now<<1|1,x,y,v);
    pushup(now);
    return ;
}
int main(){
    // freopen("wxyt4.in","r",stdin);
    // freopen("wxyt.out","w",stdout);
    n=read();q=read();W=read();
    build(1,n,1);
    while(q--){
        LL l=read(),r=read(),d=read(),w=W,ans=0,now=1,k=1;
        modify(1,n,1,l,r,d);
        while(w>sum[1]*k){
            w-=sum[1]*k;
            ans+=n;
            k<<=1;
        }
        //以下为线段树二分
        l=1,r=n;
        while(l!=r){
            LL mid=l+r>>1;
            pushdown(l,r,now);//注意在此处下传懒标记
            if(sum[now<<1]*k<w)ans+=mid-l+1,w-=sum[now<<1]*k,l=mid+1,now=now<<1|1;
            else r=mid,now<<=1;
        }
        printf("%lld\n",ans);
    }
    return 0;
}