1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
| #define int long long
#define maxn 100005
int n,q,c[maxn],b[maxn],a[maxn],s[maxn];
set<int>tr;
struct node{
int l,r,t;
node(int a=0,int b=0,int c=0) {l=a;r=b;t=c;}
bool operator <(const node &x) const {return r<x.r;}
}tmp;
set<node>t;
vector<int>O[maxn];
const int base=1e5+1;
struct yyy{
int ls,rs,sum;
}f[maxn*100];
int rt1[maxn],rt2[maxn],cnt;
namespace seg{
int Update(int l,int r,int pre,int head,int k) {
int rt=++cnt;f[rt]=f[pre];f[rt].sum+=k;
if (l==r) return rt;
int mid=l+r>>1;
if (head<=mid) f[rt].ls=Update(l,mid,f[rt].ls,head,k);
else f[rt].rs=Update(mid+1,r,f[rt].rs,head,k);
return rt;
}
int Query(int l,int r,int rt,int head,int tail) {
if (!rt) return 0;
if (head<=l&&r<=tail) return f[rt].sum;
int mid=l+r>>1,tmp=0;
if (head<=mid) tmp+=Query(l,mid,f[rt].ls,head,tail);
if (tail>mid) tmp+=Query(mid+1,r,f[rt].rs,head,tail);
return tmp;
}
}
int calc(int l,int r,int t1,int t2) {
int len=min(t2-t1,base);
int sum=seg::Query(1,n,rt1[len],l,r)*(t2-t1)+seg::Query(1,n,rt2[len],l,r);
return sum;
}
signed main(void){
int i,x,y,times,l,r;
read(n);
for (i=1;i<=n;i++) {
read(c[i]),read(a[i]),read(b[i]);
if (b[i]) O[a[i]/b[i]+1].push_back(i);
}
for (i=1;i<=n;i++) tr.insert(i);
for (i=1;i<=n;i++) rt1[0]=seg::Update(1,n,rt1[0],i,b[i]);
for (i=1;i<=base;i++) {
rt1[i]=rt1[i-1];
rt2[i]=rt2[i-1];
for (auto tmp:O[i])
rt1[i]=seg::Update(1,n,rt1[i],tmp,-b[tmp]),rt2[i]=seg::Update(1,n,rt2[i],tmp,a[tmp]);
}
read(q);
gdb(q);
while (q--) {
read(times);read(l);read(r);
int sum=0;
auto it2=t.lower_bound(node(l,l,0)),io=it2;
if (io!=t.end()&&(*io).l<l) {
tmp=(*io);
sum+=calc(l,min(tmp.r,r),tmp.t,times);
t.erase(io);
if (tmp.l<l) t.insert(node(tmp.l,l-1,tmp.t));
if (tmp.r>r) t.insert(node(r+1,tmp.r,tmp.t));
}
for (io=t.lower_bound(node(l,l,0));io!=t.end();io=it2) {
tmp=*io;
if (tmp.r>r) break;
sum+=calc(tmp.l,tmp.r,tmp.t,times);
it2=io;it2++;
t.erase(io);
}
if (io!=t.end()&&(*io).l<=r) {
tmp=*io;
sum+=calc(tmp.l,r,tmp.t,times);
t.erase(io);
if (r<tmp.r) t.insert(node(r+1,tmp.r,tmp.t));
}
auto it=tr.lower_bound(l);
while (it!=tr.end()&&(*it)<=r) {
int id=*it;sum+=min(c[id]+b[id]*times,a[id]);
tr.erase(it);it=tr.lower_bound(l);
}
t.insert(node(l,r,times));
printf("%lld\n",sum);
}
return 0;
}
|