The sol of 《youyou 的垃圾桶》
The sol of 《youyou 的垃圾桶》
https://www.luogu.com.cn/problem/P11217?contestId=203482
https://oier.team/problems/85
思路
正解貌似是差分，但可以比较无脑地用线树上二分来做（乱搞的快感）
解题方法
用线段树处理每次强化的攻击力；
先预处理出前缀和，然后先用攻击力不断翻倍，用总生命值去减，剩下的不能用整段处理的生命值去二分地求前缀和（记得要乘上倍数）。
要在线段树上二分，这样是 $ 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;
}