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

徐振轩2011 · 2024-10-20 21:43:21 · 题解

P11217题解

Part 0 致谢：

感谢 mengzdd 大佬对该题解提出的宝贵建议。

Part 1 读题 & 分析

该题解做法：线段树 + 二分。

题目大意：

youyou 要去打仗，打仗前有一部分敌人的战斗力会上升，接着，youyou 会一个接着一个打过去，直到 Ta 死了，当 youyou 战胜了一个敌人之后（剩余血量无法被那个敌人一击致命），那个敌人便会重新“满血复活”，并且战斗力提高至原来的 2 倍，求 youyou 最多能打倒多少个敌人 （最后一个不算，一个敌人可以被打多次）。

看到这里，我们可以发现，要实现两种操作，区间修改和区间查询，所以我们立刻想到了线段树。

Part 2 修改

题目要求在战斗开始前要修改一部分连续垃圾桶的战斗力，这是一个线段树十分典型的运用（就是板子），不会的请出门左转：【模板】线段树1 。

Part 3 计算评分

我们可以发现，youyou 打敌人时，肯定是先打了 k（k \ge 0）轮之后，又打了几个敌人，因为敌人的战斗力是在不断翻倍的，所以 k \le \log W（最坏情况是只有一个敌人，初始战斗力为 1 ），所以我们先统计出 x 的值（x = \sum_{i = 1}^{n} a_i ，即为所有垃圾桶再修改后的初始战斗力之和），再去暴力枚举，代码如下：

int level = 1;
int ans = 0;
int blood = w;
int all = query(1,1,n,1,n); // 统计战斗力之和，query函数见下面 
while(1){
    if (blood <= all) break; // 如果剩余血量不够杀一整排敌人了，退出循环 
    blood -= all; // 扣血 
    all *= 2; // 因为敌人的血量会翻倍，所以要乘 2 
    ans += n; // 又战胜了 n 个敌人 
    level *= 2;
}

接下来我们要统计，youyou 还能杀多少个敌人，于是我们立刻就想到了二分。

但是我们会发现，我们并没有修改战斗力，因为所有敌人的战斗力都乘上了 2^k（k 的定义见上方），所以我们只需要维护一个变量，计算这些敌人的战斗力翻了的倍数即可，这就解释了上面的这条语句：level *= 2;

二分代码如下：

int L = 1,R = n,tmid,p = 0;
    while(L <= R){
        tmid = (L + R) >> 1;
    if (query(1,1,n,1,tmid) * level < blood){
        p = tmid;
        L = tmid + 1;
    }else{
        R = tmid - 1;
    }
}

Part 4 优化

我们会发现，计算评分的时间复杂度是 O(q \log^2 n) 的，会被卡掉，所以考虑优化。

二分放在外面是十分浪费时间的，我们可以直接对线段树进行二分，如果左儿子的权值大于所求权值，则递归右子树，否则递归左子树，做法显然是正确的。

但是，还是有一点坑的，比如这个。

你不能写成这样：

if (blo >= sum[o << 1] * lev) return query2(o << 1 | 1,mid + 1,r,lev,blo - sum[o << 1] * lev);

而应该写成这样：

if (blo > sum[o << 1] * lev) return query2(o << 1 | 1,mid + 1,r,lev,blo - sum[o << 1] * lev);

这是因为，最后一个不算，如果一个人的血量刚好能被那个敌人击败，那么是不算的，所以不能写成大于等于号。

最后的答案显然是 nk + p - 1（p 表示 youyou 在战斗了 k 轮 后，还能杀多少个敌人）。

闲话：如果你写成了 blo >= sum[o << 1] * lev ，你过不了第一个样例，但是可以 AC，所以本题 hack 数据就是第一个样例（赛时）。

本部分代码：

int query2(int o,int l,int r,int lev,int blo){
    if (l == r) return l; // 返回最多能打到的编号
    int mid = (l + r) >> 1;
    pushdown(o,l,r);
    if (blo > sum[o << 1] * lev) return query2(o << 1 | 1,mid + 1,r,lev,blo - sum[o << 1] * lev); // 左儿子的权值大于所求权值，递归右子树，不要忘记血量要减少
    else return query2(o << 1,l,mid,lev,blo); // 递归左子树
}

Part 5 AC Code

时间复杂度是 O(q \log W + q \log n)。

线段树空间开 4 倍！！！

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5 + 10;
int n,q,w;
int a[N],sum[N << 2],lzy[N << 2];
void pushup(int o){
    sum[o] = sum[o << 1] + sum[o << 1 | 1];
}
void build(int o,int l,int r){
    if (l == r){
        sum[o] = a[l];
        return;
    }
    int mid = (l + r) >> 1;
    build(o << 1,l,mid);
    build(o << 1 | 1,mid + 1,r);
    pushup(o);
}
void pushdown(int o,int l,int r){
    int mid = (l + r) >> 1;
    sum[o << 1] += lzy[o] * (mid - l + 1);
    sum[o << 1 | 1] += lzy[o] * (r - mid);
    lzy[o << 1] += lzy[o];
    lzy[o << 1 | 1] += lzy[o];
    lzy[o] = 0;
}
void update(int o,int l,int r,int ql,int qr,int x){
    if (ql <= l && r <= qr){
        sum[o] += (r - l + 1) * x;
        lzy[o] += x;
        return;
    }
    int mid = (l + r) >> 1;
    pushdown(o,l,r);
    if (ql <= mid) update(o << 1,l,mid,ql,qr,x);
    if (qr > mid) update(o << 1 | 1,mid + 1,r,ql,qr,x);
    pushup(o);
}
int query(int o,int l,int r,int ql,int qr){
    if (ql <= l && r <= qr)
        return sum[o];
    int mid = (l + r) >> 1;
    int ret = 0;
    pushdown(o,l,r);
    if (ql <= mid) ret += query(o << 1,l,mid,ql,qr);
    if (qr > mid) ret += query(o << 1 | 1,mid + 1,r,ql,qr);
    return ret;
}
int query2(int o,int l,int r,int lev,int blo){
    if (l == r) return l;
    int mid = (l + r) >> 1;
    pushdown(o,l,r);
    if (blo > sum[o << 1] * lev) return query2(o << 1 | 1,mid + 1,r,lev,blo - sum[o << 1] * lev);
    else return query2(o << 1,l,mid,lev,blo);
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> q >> w;
    for (int i = 1 ; i <= n ; i++) cin >> a[i];
    build(1,1,n);
    for (int i = 1 ; i <= q ; i++){
        int l,r,d;
        cin >> l >> r >> d;
        update(1,1,n,l,r,d);
        int level = 1;
        int ans = 0;
        int blood = w;
        int all = query(1,1,n,1,n);
        while(1){
            if (blood <= all) break;
            blood -= all;
            all *= 2;
            ans += n;
            level *= 2;
        }
        int p = query2(1,1,n,level,blood);
        cout << ans + p - 1 << '\n';
    }
    return 0;
}