将$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 }