S2T1 youyou 的垃圾桶

xianghaoyu666 · 2025-10-10 21:41:01 · 个人记录

P11217 youyou 的垃圾桶题解

题目传送门

分析

youyou 死亡时，必定时被垃圾桶打了几轮，再在最后被前几个垃圾桶干掉

所以可以枚举前面的轮数，再枚举最后的垃圾桶数，一定要记得答案-1

时间复杂度 O(qn\log_2W)

预计 20pts

优化

::::info[小结论]{open} 对于每一个垃圾桶来说，它打满 n 轮，造成的总伤害为

a_i \times 2^0 + a_i \times 2^1+...+a_i \times 2^{n-1}

提公因数

a_i \times (2^0+2^1+...+2^{n-1})

可得

a_i \times (2^n-1)

::::

所以，我们要找到的是第一个 \geqslant W 的总伤害

即 \sum\limits_{i=1}^n a_i \times (2^{x}-1) \leqslant W 的最大 x

设 \sum\limits_{i-1}^{n} a_i = sum

则 sum \times (2^x-1) \leqslant W

得 2^x-1 \leqslant \frac{W}{sum}

即 2^x \leqslant \frac{W}{sum} + 1

就是 x \leqslant \log_2{(\frac{W}{sum}+1)}

因为 x 是正整数，所以用向下取整，剩下的留给最后一轮
x = \lfloor \log_2{(\frac{W}{sum}+1)} \rfloor
可证明 \lfloor \log_2{(\frac{W}{sum}+1)} \rfloor = \lfloor \log_2{( \lfloor \frac{W}{sum}+1 \rfloor ) } \rfloor

实现为
int x=floor(log2(1.0*(w+sum)/sum));
更新 O(n) ，查询 O(n)

总时间复杂度为 O(qn)

预计得分 35pts

大优化

从更新优化：快速对一段区间更新，可用差分、线段树，差分查询 O(n) ，不合适，所以用线段树
查询：既然是线段树，最后一行就不用从1累加了，由于答案满足单调性，可用二分

bool check(int x,int y){
    int sum=query(1,1,x);
    return sum*((1ll<<y))>=now;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>q>>w;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        sum+=a[i];//累加和
    }
    build(1,1,n);
    while(q--){
        ans=0;
        int l,r,d;
        cin>>l>>r>>d;
        sum+=(r-l+1)*d;//和更新
        upd(1,l,r,d);
        int x=floor(log2(1.0*(w+sum)/sum));//算轮数
        ans+=n*x;
        now=w-sum*((1ll<<x)-1);//剩下的血量
        int anss=0;
        int ll=0,rr=n+1;
        while(ll<=rr){
            int mid=ll+rr>>1;//mid为最后一行的垃圾桶数
            if(check(mid,x)){
                rr=mid-1;
                anss=mid;
            }else{
                ll=mid+1;
            }
        }
        cout<<ans+anss-1<<endl;
    }
    return 0;
}

时间复杂度 O(q\log_2^2n)

大概 60-70pts

小优化

根据题目， O(q\log_2 n) 可以过

主要瓶颈在二分+线段树

能否把两个log并在一起呢？

把二分塞进线段树，因为只需要1-x，所以在线段树中向左或右儿子递归，最终返回受致命一击的垃圾桶下标再加上 n \times x - 1即可

实现

int query(int x,int a/*血量*/,int b/*轮数*/){
    if(t[x].v*(pw2[b-1])<=a || t[x].l==t[x].r){//这些垃圾桶打完才死或没死
        return t[x].r-t[x].l+1;
    }
    push_down(x);
    if(a<=t[ls].v*(pw2[b-1])){//在左儿子打死
        return query(ls,a,b);
    }else{//在右儿子打死
        return t[ls].r-t[ls].l+1+query(rs,a-t[ls].v*(pw2[b-1]),b);
    }
    return 0;
}

时间复杂度 O(q\log_2n)

100pts

AC code

::::success[AC] 记录

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define ls x<<1
#define rs x<<1|1
using namespace std;
const int N=2e5+10;
int n,q,w,sum;
int a[N],pw2[110];
int ans;
int now;
struct node{
    int l,r,v,tag;
}t[N<<2];
void push_up(int x){
    t[x].v=t[ls].v+t[rs].v;
    return;
} 
void push_down(int x){
    t[ls].v+=(t[ls].r-t[ls].l+1)*t[x].tag;
    t[rs].v+=(t[rs].r-t[rs].l+1)*t[x].tag;
    t[ls].tag+=t[x].tag;
    t[rs].tag+=t[x].tag;
    t[x].tag=0;
    return;
}
void build(int x,int l,int r){
    t[x].l=l;
    t[x].r=r;
    t[x].tag=0;
    if(l==r){
        t[x].v=a[l];
        return;
    }
    int mid=l+r>>1;
    build(ls,l,mid);
    build(rs,mid+1,r);
    push_up(x);
    return;
}
void upd(int x,int l,int r,int k){
    if(l<=t[x].l && t[x].r<=r){
        t[x].v+=(t[x].r-t[x].l+1)*k;
        t[x].tag+=k;
        return;
    }
    push_down(x);
    int mid=t[x].l+t[x].r>>1;
    if(l<=mid){
        upd(ls,l,r,k);
    }
    if(r>mid){
        upd(rs,l,r,k);
    }
    push_up(x);
    return;
}
int query(int x,int a/*血量*/,int b/*轮数*/){
//  cout<<t[x].l<<' '<<t[x].r<<' '<<t[x].v*(pw2[b-1])<<' '<<a<<' '<<b<<endl;
    if(t[x].v*(pw2[b-1])<=a || t[x].l==t[x].r){
        return t[x].r-t[x].l+1;
    }
    push_down(x);
    if(a<=t[ls].v*(pw2[b-1])){
        return query(ls,a,b);
    }else{
        return t[ls].r-t[ls].l+1+query(rs,a-t[ls].v*(pw2[b-1]),b);
    }
    return 0;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>q>>w;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        sum+=a[i];
    }
    pw2[0]=1;
    for(int i=1;i<=62;i++){
        pw2[i]=pw2[i-1]*2;
    }
    build(1,1,n);
    while(q--){
        ans=0;
        int l,r,d;
        cin>>l>>r>>d;
        sum+=(r-l+1)*d;
        upd(1,l,r,d);
        int x=floor(log2(1.0*(w+sum)/sum));
        ans+=n*x;
        now=w-sum*(pw2[x]-1);
        int anss=0;
        int ll=0,rr=n+1;
        cout<<ans+(now==0?0:query(1,now,x+1))-1<<endl;
    }
    return 0;
}

::::

散花！！！

S2T1 youyou 的垃圾桶

P11217 youyou 的垃圾桶 题解

分析

优化

大优化

小优化

AC code

P11217 youyou 的垃圾桶题解