将$n$类物品按照价值为第一关键字（从大到小）、质量为第二关键字（从小到大）排序，此时贪心策略即依次贪心选（排序后）第$i$类的物品（其中$i$从1到$n$）
为了方便，排序后第$i$类物品质量、价值和个数仍用$w_{i},v_{i}$和$a_{i}$描述（即默认初始排序）
$\forall 0\le k\le 30$，维护一棵线段树，其中区间$[l,r]$维护：
1.$\sum_{l\le i\le r,w_{i}<2^{k}}a_{i}w_{i}$和$\sum_{l\le i\le r,w_{i}<2^{k}}a_{i}v_{i}$（特别的，若$w_{i}\ge 2^{k}$则$a_{i}$强制为0）
2.$\min_{l\le j\le r,2^{k}\le w_{j}<w^{k+1},a_{j}\ge 1}(\sum_{l\le i<j,w_{i}<2^{k}}a_{i}w_{i}+w_{j})$（特别的，若不存在$j$则强制为$\infty$）
修改操作会影响$o(\log n)$棵线段树，单次修改复杂度即$o(\log^{2}n)$
设已经贪心到第$l$类物品（第$l$类还未贪心），箱子剩余的容纳质量为$c$，取最大的$0\le k\le 30$满足$c\ge 2^{k}$
考虑找到最小的$r$，满足$\min_{l\le j\le r,2^{k}\le w_{j}<w^{k+1},a_{j}\ge 1}(\sum_{l\le i<j,w_{i}<2^{k}}a_{i}w_{i}+w_{j})\le c$，通过在$k$对应的线段树上二分即可做到$o(\log n)$的复杂度
若存在这样的$r$，此时即将$c$减去$\sum_{l\le i<r,w_{i}<2^{k}}a_{i}w_{i}+w_{r}$，答案增加$\sum_{l\le i<r,w_{i}<2^{k}}a_{i}v_{i}+v_{r}$
若不存在这样的$r$，再找到最小的$r$，满足$\sum_{l\le i\le r,w_{i}<2^{k}}a_{i}w_{i}>c$，同样在线段树上二分实现
此时即将$c$减去$\sum_{l\le i<r,w_{i}<2^{k}}a_{i}w_{i}$，答案增加$\sum_{l\le i<r,w_{i}<2^{k}}a_{i}v_{i}$，再手动贪心第$r$类物品（特别的，若$r>n$则跳过这一步）
最终，再把$l$变为$r+1$即可
关于正确性，分析如下——
对于第一种情况，即选择了$[l,r)$中所有$w_{i}<2^{k}$的物品，也即求证若$r’$满足$l\le r'<r$且$w_{r’}\ge 2^{k}$，$w_{r’}$必然不会被选择，对$w_{r’}$的情况分类讨论：
1.$w_{r’}<2^{k+1}$，此时如果会被选择，显然将$r$变为$r’$更优
2.$w_{r’}\ge 2^{k+1}$，若$c=30$显然不存在此类物品，否则必然有$c<2^{k+1}$，也不能被选择
而对于$w_{r}$，上述式子的最小值必然在$j=r$时取到（否则令$r$为取到最小值的$j$更优），即$w_{r}\ge 2^{k}$，因此$w_{r}$至多选择一个，且可以被选择，即选择一个即可
对于第二种情况，由于不存在$r$，也即一定不能选择$w_{i}\ge 2^{k}$的物品，因此仅考虑$w_{i}<2^{k}$的物品即可
关于最后的手动贪心，若$w_{r}\ge 2^{k}$显然将$r$变为$r+1$更优，因此必然有$w_{r}<2^{k}$，且一定不能全部选择（同样将$r$变为$r+1$更优）
关于时间复杂度，分析如下——
事实上，不论哪一种情况，最终都会有$c<2^{k}$或$l>n$
第一种情况，由于选择了$w_{r}\ge 2^{k}$的物品，显然$c<2^{k}$
第二种情况，由于最终手动贪心第$r$类物品，根据前面的分析$w_{r}<2^{k}$且不能全部选择，那么最终若$c\ge 2^{k}$则还可以再选一个$w_{r}$的物品（特别的，若$r>n$即$l>n$）
由此，上述过程至多执行$o(\log n)$次，单次询问复杂度即$o(\log^{2}n)$
综上，总时间复杂度为$o(n\log^{2}n)$，可以通过
1 #include<bits/stdc++.h>
2 using namespace std;
3 #define N 200005
4 #define ll long long
5 #define L (k<<1)
6 #define R (L+1)
7 #define mid (l+r>>1)
8 struct Thing{
9 int a,w,v,id;
10 bool operator < (const Thing &k)const{
11 return ((v>k.v)||(v==k.v)&&(w<k.w));
12 }
13 }a[N];
14 struct Data{
15 ll w,v,mn;
16 }o,f[31][N<<2];
17 int n,q,p,x,y,id[N];
18 ll z;
19 void get(int k,int x){
20 for(int i=0;i<=30;i++){
21 f[i][k]=o;
22 if (a[x].w<(1<<i)){
23 f[i][k].w=1LL*a[x].a*a[x].w;
24 f[i][k].v=1LL*a[x].a*a[x].v;
25 }
26 else{
27 if ((i<30)&&(a[x].w<(1<<i+1))&&(a[x].a>=1))f[i][k].mn=a[x].w;
28 }
29 }
30 }
31 Data merge(Data x,Data y){
32 return Data{x.w+y.w,x.v+y.v,min(x.mn,y.mn+x.w)};
33 }
34 void up(int k){
35 for(int i=0;i<=30;i++)f[i][k]=merge(f[i][L],f[i][R]);
36 }
37 void build(int k,int l,int r){
38 if (l==r){
39 get(k,l);
40 return;
41 }
42 build(L,l,mid);
43 build(R,mid+1,r);
44 up(k);
45 }
46 void update(int k,int l,int r,int x){
47 if (l==r){
48 get(k,x);
49 return;
50 }
51 if (x<=mid)update(L,l,mid,x);
52 else update(R,mid+1,r,x);
53 up(k);
54 }
55 Data query(int p,int k,int l,int r,int x,int y){
56 if ((l>y)||(x>r))return o;
57 if ((x<=l)&&(r<=y))return f[p][k];
58 return merge(query(p,L,l,mid,x,y),query(p,R,mid+1,r,x,y));
59 }
60 int find1(int p,int k,int l,int r,int x,ll &y){//找到大于等于x的位置中第一个mn<=y的位置
61 if (r<x)return n+1;
62 if ((l>=x)&&(f[p][k].mn>y)){
63 y-=f[p][k].w;
64 return n+1;
65 }
66 if (l==r)return l;
67 int ans=find1(p,L,l,mid,x,y);
68 if (ans<=n)return ans;
69 return find1(p,R,mid+1,r,x,y);
70 }
71 int find2(int p,int k,int l,int r,int x,ll &y){//找到大于等于x的位置中第一个w>y的位置
72 if (r<x)return n+1;
73 if ((l>=x)&&(f[p][k].w<=y)){
74 y-=f[p][k].w;
75 return n+1;
76 }
77 if (l==r)return l;
78 int ans=find2(p,L,l,mid,x,y);
79 if (ans<=n)return ans;
80 return find2(p,R,mid+1,r,x,y);
81 }
82 ll query(ll c){
83 int pos=1;
84 ll cc,ans=0;
85 while ((pos<=n)&&(c)){
86 int k=0,nex;
87 for(int i=0;i<=30;i++)
88 if ((1<<i)<=c)k=i;
89 nex=find1(k,1,1,n,pos,cc=c);
90 if (nex<=n){
91 Data o=query(k,1,1,n,pos,nex-1);
92 c-=o.w+a[nex].w,ans+=o.v+a[nex].v;
93 }
94 else{
95 nex=find2(k,1,1,n,pos,cc=c);
96 Data o=query(k,1,1,n,pos,nex-1);
97 c-=o.w,ans+=o.v;
98 if (nex<=n){
99 ll s=c/a[nex].w;
100 c-=s*a[nex].w,ans+=s*a[nex].v;
101 }
102 }
103 pos=nex+1;
104 }
105 return ans;
106 }
107 int main(){
108 o.mn=2e18;
109 scanf("%d%d",&n,&q);
110 for(int i=1;i<=n;i++){
111 scanf("%d%d%d",&a[i].a,&a[i].w,&a[i].v);
112 a[i].id=i;
113 }
114 sort(a+1,a+n+1);
115 for(int i=1;i<=n;i++)id[a[i].id]=i;
116 build(1,1,n);
117 for(int i=1;i<=q;i++){
118 scanf("%d",&p);
119 if (p==1){
120 scanf("%d%d",&x,&y);
121 y=id[y];
122 a[y].a+=x;
123 update(1,1,n,y);
124 }
125 if (p==2){
126 scanf("%d%d",&x,&y);
127 y=id[y];
128 a[y].a-=x;
129 update(1,1,n,y);
130 }
131 if (p==3){
132 scanf("%lld",&z);
133 printf("%lld\n",query(z));
134 }
135 }
136 }
