题意：有$n$个马，第$i$个马有初始能量$s_i$，每单位时间增加$r_i$，上限是$m_i$，多组询问$(t,l,r)$询问在时间$t$时$[l,r]$的能量和，询问完后把这段区间清零，保证$t$递增

两个月前曾经看到过这个题，当时看了官方题解+看了某神犇的中文题解之后觉得是不可做题所以就鸽了，今天回来一看原来还有这么简单的做法

直接上线段树，每个线段树节点存①最后被访问的时间$last$，没访问过记为$-2$，之前在不同时间被深♂入访问过记为$-1$②当前区间内的所有马，按照从零开始需要多少时间到达上限从小到大排序③$m$和$r$的前缀和

建树直接建，排个序然后处理前缀和，标记记为$-2$

询问时，设访问时间为$T$，访问到节点$x$，代表区间$[l,r]$

①若$last_x=-1$或询问区间未完整包含$[l,r]$，直接递归左右两边处理

②若$last_x=-2$，暴力计算答案，更新$last_x=T$

③若$last_x\geq0$，在当前区间内二分找到最后一个在$T-last_x$时间内会到达上限的马，前半部分答案为$\sum m$，后半部分答案为$\left(T-last_x\right)\sum r$，最后更新$last_x=T$

pushup：如果两个儿子标记相同，复制上来，否则记当前节点的标记为$-1$

pushdown：如果当前节点标记$\geq0$，直接往下覆盖标记

核心思想就是：除了第一次，后面每一次都可以当成初始能量为$0$来做，询问完后它又自己变回$0$了

开始处理询问后不会再有点的标记变为$-2$，所以暴力计算初始时的答案是可行的

#include
     
      #include
      
       using namespace std;#define ll long long#define inf 2147483647struct data{	int s,m,r,t;	data(int x=0){t=x;}	void gao(){		scanf("%d%d%d",&s,&m,&r);		t=(r?m/r+(m%r>0):inf);	}	ll calc(ll u){return min(s+r*u,(ll)m);}}a[18][100010];int Tt[400010];ll Tm[18][400010],Tr[18][400010];bool operator<(data a,data b){return a.t
       
        >1,i;	build(l,mid,x<<1,d+1);	build(mid+1,r,x<<1|1,d+1);	for(i=l;i<=r;i++)a[d][i]=a[d+1][i];	sort(a[d]+l,a[d]+r+1);	for(i=l;i<=r;i++){		Tm[d][i]=Tm[d][i-1]+a[d][i].m;		Tr[d][i]=Tr[d][i-1]+a[d][i].r;	}}void pushdown(int x){	if(Tt[x]>=0)Tt[x<<1]=Tt[x<<1|1]=Tt[x];}void pushup(int x){	Tt[x]=Tt[x<<1];	if(Tt[x]!=Tt[x<<1|1])Tt[x]=-1;}ll query(int T,int L,int R,int l,int r,int x,int d){	int i;	ll res=0;	if(L<=l&&r<=R&&Tt[x]!=-1){		if(Tt[x]==-2){			for(i=l;i<=r;i++)res+=a[d][i].calc(T);		}else{			i=upper_bound(a[d]+l,a[d]+r+1,data(T-Tt[x]))-a[d]-1;			res=(T-Tt[x])*(Tr[d][r]-Tr[d][i])+Tm[d][i]-Tm[d][l-1];		}		Tt[x]=T;		return res;	}	pushdown(x);	i=(l+r)>>1;	if(L<=i)res+=query(T,L,R,l,i,x<<1,d+1);	if(i
        
         <<1|1,d+1);	pushup(x);	return res;}int main(){	int n,m,t,l,r;	scanf("%d",&n);	build(1,n,1,0);	scanf("%d",&m);	while(m--){		scanf("%d%d%d",&t,&l,&r);		printf("%I64d\n",query(t,l,r,1,n,1,0));	}}