自动搬运

查看原文

来自洛谷，原作者为

	ykzzldz 做自己，别管别人

搬运于2025-08-24 23:05:23，当前版本为作者最后更新于2024-10-20 19:13:56，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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

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

枚举完轮数后，我们可以知道其剩余的生命值，设为 $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;
}