闲话

一道质量不错的签到题。

题解

由于有区间操作，考虑使用线段树。

不难通过线段树维护需要区间增减操作的序列，同时不难通过二分寻找最后一个循环之后最后一个不会导致 youyou 死亡的垃圾桶。实际上，本题的难点在于 $1\le q\le 10^6$，暴力实现上述思路的时间复杂度为 $O(q\log^2 n)$，结合线段树的较大常数，通过此题需要卡常。

然而，线段树的结构决定了上述思路可以在 $O(q\log n)$ 的时间复杂度内实现。

假设线段树维护了一个长度为 $n$ 的序列 $a$。给出值 $x$，你需要找出最大的 $i$，满足 $1\le i\le n$ 且 $\sum_{j=1}^i a_j<x$。

由于线段树的每个节点有左子节点和右子节点，则你可以确定你的目标在左子节点内或右子节点内。

具体地说，若 $x$ 小于左子节点内元素之和，则你的目标在左子节点内，否则可能在右子节点内。

按照上述方法操作，遍历到线段树的叶子节点时一定可以找出答案。

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

代码

#include <cctype>
#include <cstdio>
using namespace std;
const int N = 2e5 + 10;
using ll = long long;
int n, q, a[N];
ll w, tr[N << 2], tag[N << 2];
inline void build(int x, int l, int r)
{
    if (l == r)
        return tr[x] = a[l], void();
    int mid = (l + r) >> 1;
    build(x << 1, l, mid);
    build(x << 1 | 1, mid + 1, r);
    tr[x] = tr[x << 1] + tr[x << 1 | 1];
}
void psh(int x, int l, int r)
{
    int mid = (l + r) >> 1;
    tr[x << 1] += tag[x] * (mid - l + 1);
    tr[x << 1 | 1] += tag[x] * (r - mid);
    tag[x << 1] += tag[x], tag[x << 1 | 1] += tag[x];
    tag[x] = 0;
}
void update(int x, int l, int r, int lb, int rb, ll v)
{
    if (l >= lb and r <= rb)
    {
        tr[x] += v * (r - l + 1);
        tag[x] += v;
        return;
    }
    if (tag[x])
        psh(x, l, r);
    int mid = (l + r) >> 1;
    if (lb <= mid)
        update(x << 1, l, mid, lb, rb, v);
    if (rb > mid)
        update(x << 1 | 1, mid + 1, r, lb, rb, v);
    tr[x] = tr[x << 1] + tr[x << 1 | 1];
}
int lwr(int x, int l, int r, ll v)
{
    if (l == r)
        return tr[x] >= v ? l - 1 : l;
    if (tag[x])
        psh(x, l, r);
    int mid = (l + r) >> 1;
    ll res = 0;
    if (tr[x << 1] < v)
        res = lwr(x << 1 | 1, mid + 1, r, v - tr[x << 1]);
    else
        res = lwr(x << 1, l, mid, v);
    tr[x] = tr[x << 1] + tr[x << 1 | 1];
    return res;
}
ll run()
{
    ll tmp = w, tsm = tr[1], res = 0, rd = 1;
    // printf("tsm %lld\n", tsm);
    while (tmp > tsm)
        tmp -= tsm, res += n, tsm <<= 1, rd <<= 1;
    // printf("t %lld %lld\n", res, (tmp + rd - 1) / rd);
    return res + lwr(1, 1, n, (tmp + rd - 1) / rd);
}
template <typename _Tp> inline void read(_Tp &x)
{
    char ch;
    while (ch = getchar(), !isdigit(ch) and ~ch)
        ;
    x = (ch ^ 48);
    while (ch = getchar(), isdigit(ch))
        x = (x << 3) + (x << 1) + (ch ^ 48);
}
template <typename _Tp, typename... _Args> inline void read(_Tp &x, _Args &...args)
{
    read(x);
    read(args...);
}
template <typename _Tp> inline void print(_Tp x)
{
    if (x > 9)
        print(x / 10);
    putchar((x % 10) ^ 48);
}
int main()
{
    // freopen("wxyt.in", "r", stdin);
    // freopen("wxyt.out", "w", stdout);
    read(n, q, w);
    for (int i = 1; i <= n; i++)
    {
        read(a[i]);
    }
    build(1, 1, n);
    for (int i = 1, l, r, v; i <= q; i++)
    {
        read(l, r, v);
        update(1, 1, n, l, r, v);
        print(run());
        putchar('\n');
    }
}

首先看到题目中要求进行计算前进行区间加操作，不妨考虑线段树。

对于计算分数的部分，可以将生命值分成如下两部分考虑：

1. 能够承受完整的若干轮攻击的部分。其中“一轮”表示承受 $1$ 至 $n$ 怪物的攻击。

由于怪物每攻击一次攻击力翻倍，那么我们会发现 $k$ 轮怪物 $i$ 总共造成的攻击为 $(2^0 + 2^1 + \cdots + 2 ^ {k - 1})\times a_i = (2^k - 1)\times a_i$。
那么总共能承受的轮数为 $\lfloor\log_2(\frac m{\sum_{i=1}^na_i} + 1)\rfloor$。
由此可以计算出此部分的答案。

2. 剩余的不完整部分。

很容易想到二分，但是直接二分并不好写。注意到线段树本身有二分的性质，其实已经完美解决了直接二分的问题。 这里可以把线段树当作与二叉搜索树来处理。从根节点出发往下搜，如果值比左儿子小那就走左边，否则走右边，如果走到叶节点就返回。

核心代码如下：

// k表示这一轮怪物攻击力翻了多少倍
// _rest表示剩余生命值
ll find(ll k, ll _rest, ll p = 1) {
	if (t[p].l == t[p].r) return t[p].l;
	pushdown(p);
	ll mid = t[p].l + t[p].r >> 1;
	assert(_rest < t[p].val * k);
	if (_rest <= t[p << 1].val * k) return find(k, _rest, p << 1);
	else return find(k, _rest - t[p << 1].val * k, p << 1 | 1);
}

最后记得答案减一。（战斗分数的计算不包括恰好使 youyou 死亡的垃圾桶的攻击）

时间复杂度 $O(q\log_2 n)$，可以通过本题。

code:

#include<bits/stdc++.h>
#define endl '\n'

using namespace std;

using ll = long long;

const ll N = 2e5 + 5;

ll n, q, m, a[N];

// l, r：区间左右端点
// val：线段树节点的值
// add：懒标记

struct tree {
	ll l, r;
	ll val, add;
} t[N << 2];

// p：当前线段树节点
// p << 1：左儿子
// p << 1 | 1：右儿子

void build(ll l, ll r, ll p = 1) {
	t[p].l = l; t[p].r = r;
	if (l == r) {
		t[p].val = a[l];
		return;
	}
	ll mid = l + r >> 1;
	build(l, mid, p << 1);
	build(mid + 1, r, p << 1 | 1);
	t[p].val = t[p << 1].val + t[p << 1 | 1].val;
}

void pushdown(ll p) {
	if (t[p].add) {
		t[p << 1].val += t[p].add * (t[p << 1].r - t[p << 1].l + 1);
		t[p << 1 | 1].val += t[p].add * (t[p << 1 | 1].r - t[p << 1 | 1].l + 1);
		t[p << 1].add += t[p].add;
		t[p << 1 | 1].add += t[p].add;
		t[p].add = 0;
	}
}

void update(ll l, ll r, ll z, ll p = 1) {
	if (l <= t[p].l && r >= t[p].r) {
		t[p].val += z * (t[p].r - t[p].l + 1);
		t[p].add += z;
		return;
	}
	pushdown(p);
	ll mid = t[p].l + t[p].r >> 1;
	if (l <= mid) update(l, r, z, p << 1);
	if (r > mid) update(l, r, z, p << 1 | 1);
	t[p].val = t[p << 1].val + t[p << 1 | 1].val;
}

ll query(ll l, ll r, ll p = 1) {
	if (l <= t[p].l && r >= t[p].r) return t[p].val;
	pushdown(p);
	ll mid = t[p].l + t[p].r >> 1, res = 0;
	if (l <= mid) res += query(l, r, p << 1);
	if (r > mid) res += query(l, r, p << 1 | 1);
	return res;
}

// 这里的k表示这一轮怪物攻击力翻了多少倍
ll find(ll k, ll _rest, ll p = 1) {
	if (t[p].l == t[p].r) return t[p].l;
	pushdown(p);
	ll mid = t[p].l + t[p].r >> 1;
	// assert(_rest < t[p].val * k);
	if (_rest <= t[p << 1].val * k) return find(k, _rest, p << 1);
	else return find(k, _rest - t[p << 1].val * k, p << 1 | 1);
}

void solve() {
	cin >> n >> q >> m;
	for (ll i = 1; i <= n; i++) cin >> a[i];
	build(1, n);
	while (q--) {
		ll l, r, k, _rest, ans;
		cin >> l >> r >> k;
		update(l, r, k);
		// k：轮数
		k = __lg(m / query(1, n) + 1);
		ans = k * n;
		// _rest：不满一轮的剩余生命值
		_rest = m - query(1, n) * ((1ll << k) - 1);
		if (_rest) ans += find(1ll << k, _rest);
		// cout << ans - 1 << endl;
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int _ = 1;
	// cin >> _;
	while (_--) solve();
	return 0;
}

The sol of 《youyou 的垃圾桶》

思路

正解貌似是差分，但可以比较无脑地用线树上二分来做（乱搞的快感）

解题方法

用线段树处理每次强化的攻击力； 先预处理出前缀和，然后先用攻击力不断翻倍，用总生命值去减，剩下的不能用整段处理的生命值去二分地求前缀和（记得要乘上倍数）。
要在线段树上二分，这样是 $O(q*log(n))$ 不然就有两只 $log$。
注意，要写快读，因为我写的线段数过于丑陋，被卡常了。

时间复杂度:

$O(q*log(n))$

Code

#include<bits/stdc++.h>
#define Ying using
#define AK namespace 
#define IOI std;
Ying AK IOI
#define int long long
#define ls (p<<1)
#define rs (p<<1|1)
#define len(x) (t[x].r-t[x].l+1)
#define mid ((l+r)>>1)
#define FOR(i,_l,_r) for(int i=_l;i<=_r;i++)
const int N=2e5+5;
#define il inline
il int read(){
    int x=0;
    int f=1;
    char c;
    c=getchar_unlocked();
    while(c<'0'||c>'9'){
        if(c=='-') f=-1;
        c=getchar_unlocked();
    }
    while(c>='0'&&c<='9'){
        x=x*10+c-'0';
        c=getchar_unlocked();
    }
    return x*f;
}
il void print(int x){
    if(x<0) putchar('-'),x=-x;
    if(x>9) print(x/10);
    putchar(x%10+'0');
}
int n,q,W;
int a[N];
struct node{
    int l,r,sum,tag;
}t[N<<2];
void up(int p){
    t[p].sum=t[ls].sum+t[rs].sum;
}
void Build(int p,int l,int r){
    t[p].l=l;t[p].r=r;
    if(l==r){
        t[p].sum=a[l];
        return;
    }
    Build(ls,l,mid);
    Build(rs,mid+1,r);
    up(p);
}
void spread(int p){
    if(!t[p].tag) return;
    int d=t[p].tag;
    t[ls].sum+=len(ls)*d;
    t[rs].sum+=len(rs)*d;
    t[ls].tag+=d;
    t[rs].tag+=d;
    t[p].tag=0;
}
void change(int p,int L,int R,int v){
    int l=t[p].l;
    int r=t[p].r;
    if(L<=l&&r<=R){
        t[p].sum+=v*len(p);
        t[p].tag+=v;
        return;
    }
    spread(p);
    if(L<=mid) change(ls,L,R,v);
    if(R>mid) change(rs,L,R,v);
    up(p);
}
int query(int p,int L,int R){
    int l=t[p].l;
    int r=t[p].r;
    if(L<=l&&r<=R)  return t[p].sum;
    spread(p);
    int ans=0;
    if(L<=mid) ans+=query(ls,L,R);
    if(R>mid) ans+=query(rs,L,R);
    return ans;
}
int Q(int p,int l,int r,int w,int x){
    if(l==r) return l-1;
    spread(p);
    if(t[ls].sum*x>=w) return Q(ls,l,mid,w,x);
    else return Q(rs,mid+1,r,w-t[ls].sum*x,x);
}
signed main(){
    #ifndef ONLINE_JUDGE
    freopen("wxyt.in","r",stdin);
    freopen("wxyt.out","w",stdout);
    #endif 
    ios::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    n=read();q=read();W=read();
    FOR(i,1,n) a[i]=read();
    Build(1,1,n);
    while(q--){
        int cnt=0;
        int t=0;
        int w=W;
        int x,y,k;
        x=read();y=read();k=read();
        change(1,x,y,k);
        int sum=query(1,1,n);
        while(w>=sum){
            w-=sum;
            sum<<=1;
            cnt+=n;
            t++;
        }
        if(!w){
            print(cnt-1);
            puts("");
            continue;
        }
        print(Q(1,1,n,w,(1LL<<t))+cnt);
        puts("");
    }
    return 0;
}

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