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

· · 题解

感觉这场后面的题都太神秘了。

首先看到区间加的操作，自然想到用线段树。由于每次攻击完一轮后攻击力会翻倍，这样的话，攻击力的增长速度是极快的，所以每次攻击的轮数一定不会太多，我们可以枚举这个轮数。

枚举完轮数后，我们可以知道其剩余的生命值，设为 res。剩下的生命值一定是在一轮内打完的，所以我们可以二分出在哪里打出致命伤害，再用 \log 的复杂度在线段树上查询一段前缀的和。这样，总复杂度是 O(q\log^2n) 的，期望得分 70（但据说可以使用常树小的树状数组在这个复杂度下通过）。

我们想到，每次二分出再在线段树上查询，这样的效率有点太不高了，于是考虑直接在线段树上二分，这是一个比较经典的问题，大体思路是每次在线段树上找到一个节点，如果这个节点左儿子的权值大于你所求的权值，就往左儿子走，否则往右儿子走。需要注意的是，往右儿子走的时候需要减去左儿子的权值。现在，我们就做到了 O(q\log n) 的复杂度，但由于本题比较卡常，且输入量非常大，所以记得加上快读。下面给出代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+10;
void read(int &a){
    int s=0,w=1;
    char ch=getchar();
    while(ch<'0'||'9'<ch){
        if(ch=='-')w=-1;
        ch=getchar(); 
    }
    while('0'<=ch&&ch<='9'){
        s=s*10+ch-'0';
        ch=getchar();
    }
    a=s*w;
}
int n,m,W,i,a[N];
struct tree{
    int l,r,pre,add;
}t[N<<2];
void build(int p,int l,int r){
    t[p].l=l,t[p].r=r;
    if(l==r){
        t[p].pre=a[l];
        return;
    }
    int mid=l+r>>1;
    build(p*2,l,mid);
    build(p*2+1,mid+1,r);
    t[p].pre=t[p*2].pre+t[p*2+1].pre;
}
void spread(int p){
    t[p*2].pre+=(t[p*2].r-t[p*2].l+1)*t[p].add;
    t[p*2+1].pre+=(t[p*2+1].r-t[p*2+1].l+1)*t[p].add;
    t[p*2].add+=t[p].add;
    t[p*2+1].add+=t[p].add;
    t[p].add=0;
}
void change(int p,int x,int y,int z){
    if(x<=t[p].l&&t[p].r<=y){
        t[p].pre+=(t[p].r-t[p].l+1)*z;
        t[p].add+=z;
        return;
    }
    spread(p);
    int mid=t[p].l+t[p].r>>1;
    if(x<=mid)change(p*2,x,y,z);
    if(y>mid)change(p*2+1,x,y,z);
    t[p].pre=t[p*2].pre+t[p*2+1].pre;
}
int ask(int p,int res){
    if(t[p].l==t[p].r){
        return t[p].l;
    }
    spread(p);
    int mid=t[p].l+t[p].r>>1;
    if(t[p*2].pre*(1ll<<(i-1))>=res)return ask(p*2,res);
    else return ask(p*2+1,res-t[p*2].pre*(1ll<<(i-1)));
}
signed main(){
    cin>>n>>m>>W;
    for(int j=1;j<=n;j++){
        read(a[j]);
    }
    build(1,1,n);
    while(m--){
        int l,r,d;
        read(l),read(r),read(d);
        change(1,l,r,d);
        i=0;
        int k=2,T=t[1].pre;
        for(i=1;;i++){
            int tot=T*(k-1);
            if(tot>=W)break;
            k*=2;
        }
        int res=W-T*(k/2-1);
        int ans=ask(1,res);
        printf("%lld\n",ans+(i-1)*n-1);
    }
    return 0;
}