线段树经典题

维护最大值和最小值 还有区间和

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 2e5+10;
ll w[N];
struct Segment{
	ll l,r;
	ll val,fmin,fmax;
	ll lz;
}tr[N<<2];

int n,m;



void pushup(int u){
	tr[u].val = tr[u<<1].val + tr[u<<1|1].val;
	tr[u].fmin = min(tr[u<<1].fmin,tr[u<<1|1].fmin);
	tr[u].fmax = max(tr[u<<1].fmax,tr[u<<1|1].fmax);
}

void build(int u,int l,int r){
	tr[u] = {l,r,0,0,0,0};
	if(l==r){tr[u] = {l,r,w[l],w[l],w[l],0};return;}
	int mid = l+r>>1;
	build(u<<1,l,mid),build(u<<1|1,mid+1,r);
	pushup(u);
}



void pushdown(Segment &node,int lz){
	node.lz = lz;
	node.val = (node.r-node.l+1)*lz;
	node.fmin = node.fmax = lz;
}

void pushdown(int u){
	if(tr[u].lz){
		pushdown(tr[u<<1],tr[u].lz);
		pushdown(tr[u<<1|1],tr[u].lz);
		tr[u].lz = 0;
	}
}

void modify(int u,int l,int r,int c){
	if(tr[u].l>=l&&tr[u].r<=r){
		if(tr[u].fmin>=c)return;
		if(tr[u].fmax<c){pushdown(tr[u],c);return;}
		
	}
	
	
	
	pushdown(u);
	
	int mid = tr[u].l+tr[u].r>>1;
	if(l<=mid)modify(u<<1,l,r,c);
	if(r>mid)modify(u<<1|1,l,r,c);
	
	pushup(u);

}

ll query(int u,int l,int r,ll &have){
	if(tr[u].l>=l&&tr[u].r<=r){
		if(have<tr[u].fmin)return 0;
		if(have>=tr[u].val){have-=tr[u].val;return tr[u].r-tr[u].l+1;}
		
	}
	
	pushdown(u);
	ll res = 0;
	int mid = tr[u].l+tr[u].r>>1;
	if(l<=mid)res+=query(u<<1,l,r,have);
	if(r>mid)res+=query(u<<1|1,l,r,have);
	return res;
	
}



int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>w[i];
	build(1,1,n);
	
	
	for(int i=1;i<=m;i++){
		ll op,l,r;cin>>op>>l>>r;
		if(op==1)modify(1,1,l,r);
		else cout<<query(1,l,n,r)<<"\n";
	}
	
}