本文共 1673 字，大约阅读时间需要 5 分钟。

正题

题目链接:

题目大意

$n$个树，第$i$个每天长高$a_i$米。

$m$次修剪，第$i$次在$d_i$天，将高度为$b_i$的部分修剪掉

求每次修剪掉的高度

解题思路

按照$a_i$排序后我们知道每次修改的一定是一个后缀，所以我们先考虑如何计算修改的位置。首先我们可想到类似二分的方法，为了方便维护，我们使用一个线段树，记录每个区间内最左边的树的情况，然后左右走动即可。询问时我们需要知道这个修改区间内的高度和

考虑如何储存情况，首先我们需要知道这个区间内所有树一天的成长和记为$w_i$，然后上次修改的时间$t_i$和上次修改后的高度$h_i$，那么我们就可以用$h_i\ast (r-l+1)+(T-t_i)\ast w_i$表示现在的高度和。同理最左边的树也可以这样来计算

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

$code$

#include
   
    #include
    
     #include
     
      #define ll long longusing namespace std;const ll N=5e5+10,M=4*N;ll n,m,a[N],d[N],b[N],T,answer;ll w[M],t[M],h[M],lazy[M],ans[M];void Build(ll x,ll l,ll r){
   	if(l==r){
   		w[x]=a[l];		return;	}	ll mid=(l+r)>>1;	Build(x*2,l,mid);	Build(x*2+1,mid+1,r);	w[x]=w[x*2]+w[x*2+1];}void updata(ll x,ll l,ll r,ll T){
   	t[x]=d[T];h[x]=b[T];lazy[x]=T;	ans[x]=h[x]*(r-l+1)-w[x]*t[x];}void Change(ll x,ll l,ll r){
   	if(l==r){
   		if(h[x]+(d[T]-t[x])*a[r]>b[T]){
   			answer+=h[x]+(d[T]-t[x])*a[r]-b[T];			updata(x,l,r,T);		}		return;	}	ll mid=(l+r)>>1;	if(lazy[x]){
   		updata(x*2,l,mid,lazy[x]);		updata(x*2+1,mid+1,r,lazy[x]);		lazy[x]=0;	}	if(h[x*2+1]+(d[T]-t[x*2+1])*a[mid+1]>b[T]){
   		ll z=x*2+1;		Change(x*2,l,mid);		answer+=d[T]*w[x*2+1]+ans[x*2+1]-(r-mid)*b[T];		updata(x*2+1,mid+1,r,T);	}	else Change(x*2+1,mid+1,r);	ans[x]=ans[x*2]+ans[x*2+1];	h[x]=h[x*2];t[x]=t[x*2];	return;}int main(){
   	scanf("%lld%lld",&n,&m);	for(ll i=1;i<=n;i++)		scanf("%lld",&a[i]);	sort(a+1,a+1+n);	Build(1,1,n);	for(T=1;T<=m;T++){
   		answer=0;		scanf("%lld%lld",&d[T],&b[T]);		Change(1,1,n);		printf("%lld\n",answer); 	}}
     
    
   

转载地址：http://pdwaf.baihongyu.com/