考虑如果每次都是全局修改就很简单
按照到达上限的时间排序
则前面一段满了，后面一段都没满
每次二分即可
第一次特殊处理
每次修改一个区间
考虑维护该区间是否上一次完全修改、不完全修改、没有修改过
如果是完全修改则直接计算答案，否则递归子树
同样特殊处理每个节点的第一次完全修改
这样复杂度是均摊的
#include<bits/stdc++.h>
using namespace std;
const int RLEN=1<<20|1;
inline char gc(){
static char ibuf[RLEN],*ib,*ob;
(ob==ib)&&(ob=(ib=ibuf)+fread(ibuf,1,RLEN,stdin));
return (ob==ib)?EOF:*ib++;
}
#define gc getchar
inline int read(){
char ch=gc();
int res=0,f=1;
while(!isdigit(ch))f^=ch=='-',ch=gc();
while(isdigit(ch))res=(res+(res<<2)<<1)+(ch^48),ch=gc();
return f?res:-res;
}
#define ll long long
#define re register
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back
#define cs const
#define bg begin
inline void chemx(int &a,int b){a<b?a=b:0;}
inline void chemn(int &a,int b){a>b?a=b:0;}
struct node{
int s,m,r,t;
node(int _s=0,int _m=0,int _r=0,int _t=0):s(_s),m(_m),r(_r),t(_t){}
friend inline bool operator <(cs node &a,cs node &b){
return a.t<b.t;
}
friend inline bool operator ==(cs node &a,cs node &b){
return a.t==b.t;
}
friend inline bool operator >(cs node &a,cs node &b){
return a.t>b.t;
}
friend inline bool operator <=(cs node &a,cs node &b){
return a.t<=b.t;
}
friend inline bool operator >=(cs node &a,cs node &b){
return a.t>=b.t;
}
friend inline bool operator !=(cs node &a,cs node &b){
return a.t!=b.t;
}
};
cs int N=100005,inf=2e9;
node a[N];
int n,q;
struct Tr{
vector<node> v;
vector<ll> sl,sr;
int last;
inline void init(int l,int r){
int len=r-l+1;
for(int i=l;i<=r;i++)v.pb(a[i]);
sort(v.bg(),v.end());
sl.resize(len),sr.resize(len);
sl[0]=v[0].m,sr[len-1]=v[len-1].r;
for(int i=1;i<len;i++)sl[i]=sl[i-1]+v[i].m;
for(int i=len-2;~i;i--)sr[i]=sr[i+1]+v[i].r;
}
inline ll query(int t){
int tim=t-last;
int pos=lower_bound(v.bg(),v.end(),node(0,0,0,tim))-v.bg()-1;
ll res=0;
if(~pos)res+=sl[pos];
if(pos+1<(int)v.size())res+=sr[pos+1]*tim;
last=t;return res;
}
};
namespace Seg{
Tr tr[N<<2];
#define lc (u<<1)
#define rc ((u<<1)|1)
#define mid ((l+r)>>1)
void build(int u,int l,int r){
tr[u].last=-2,tr[u].init(l,r);
if(l==r)return;
build(lc,l,mid),build(rc,mid+1,r);
}
inline void pushup(int u){
if(tr[lc].last==tr[rc].last)
if(tr[lc].last>=0){tr[u].last=tr[lc].last;return;}
else if(tr[lc].last==-2){tr[u].last=-2;return;}
tr[u].last=-1;
}
inline void pushdown(int u){
if(tr[u].last>=0)
tr[lc].last=tr[rc].last=tr[u].last;
}
ll query(int u,int l,int r,int st,int des,int k){
if(l==r&&tr[u].last==-2){tr[u].last=k;return min(1ll*a[l].m,1ll*a[l].s+1ll*a[l].r*k);}
if(st<=l&&r<=des&&tr[u].last>=0)return tr[u].query(k);
ll res=0;pushdown(u);
if(st<=mid)res+=query(lc,l,mid,st,des,k);
if(mid<des)res+=query(rc,mid+1,r,st,des,k);
pushup(u);
return res;
}
}
int main(){
n=read();
for(int i=1;i<=n;i++){
a[i].s=read(),a[i].m=read(),a[i].r=read(),a[i].t=a[i].r==0?inf:a[i].m/a[i].r;
}
Seg::build(1,1,n);
q=read();
while(q--){
int t=read(),l=read(),r=read();
cout<<Seg::query(1,1,n,l,r,t)<<'
';
}
}