S4A 题解

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;
}