小 N 是蔬菜仓库的管理员，负责设计蔬菜的销售方案。 在蔬菜仓库中，共存放有 n 种蔬菜，小 N 需要根据不同蔬菜的特性，综合考虑各 方面因素，设计合理的销售方案，以获得最多的收益。 在计算销售蔬菜的收益时，每销售一个单位第 i 种蔬菜，就可以获得 ai 的收益。 特别地，由于政策鼓励商家进行多样化销售，第一次销售第 i 种蔬菜时，还会额外 得到 si 的额外收益。 在经营开始时，第 i 种蔬菜的库存为 ci 个单位。 然而，蔬菜的保鲜时间非常有限，一旦变质就不能进行销售，不过聪明的小 N 已 经计算出了每个单位蔬菜变质的时间：对于第 i 种蔬菜，存在保鲜值 xi，每天结束时会 有 xi 个单位的蔬菜变质，直到所有蔬菜都变质。（注意：每一单位蔬菜的变质时间是固 定的，不随销售发生变化） 形式化地：对于所有的满足条件 d × xi ≤ ci 的正整数 d ，有 xi 个单位的蔬菜将在 第 d 天结束时变质。 特别地，若 (d − 1) × xi ≤ ci < d × xi ，则有 ci − (d − 1) × xi 单位的蔬菜将在第 d 天 结束时变质。 注意，当 xi = 0 时，意味着这种蔬菜不会变质。 同时，每天销售的蔬菜总. 量. 也是有限的，最多不能超过 m 个单位。 现在，小 N 有 k 个问题，想请你帮忙算一算。每个问题的形式都是：对于已知的 pj，如果需要销售 pj 天，最多能获得多少收益？
Solution
这题好神，研究了半天题解。
先考虑只有一组询问的情况。
因为一种蔬菜第一次出售和之后再出售价格不同，所以我们把一种蔬菜拆成两个。
这样的话我们就可以按照权值从大到小排序，再贪心就可以了。
对于一种蔬菜，我们可以把它从坏掉的那一天贪心的能放就放(这样肯定是对的，因为那个位置卖后面的东西肯定是不优的).。
然后用并查集维护能卖的天。
还需要注意我们是用了时光倒流的思想，在一开始枚举时候，我们的蔬菜量是坏到那一天时的剩余蔬菜量，再往前跳下一个能卖东西的日子时，要把这段时间内的坏掉的蔬菜加回来。
这就是对于一个询问的操作。
再考虑多组询问。
我们取天数最大的一个询问，对它做一遍贪心，与此同时开两个桶记录每天卖了多少蔬菜和每种蔬菜卖了多少份。
然后我们在缩短时间时维护一个东西，就是对于一天来说最少需要丢掉几个蔬菜,其实就是这一天往后卖的所有蔬菜减去前面还能卖的蔬菜。
然后我们贪心的挑小的丢掉就好了。
Code
#include<iostream> #include<cstdio> #include<queue> #include<algorithm> #define N 200002 using namespace std; typedef long long ll; ll n,m,k,cnt,tong[N],ji[N],tag[N],f[N],a,x,c,s,md,sum,sh[N],to[N],diss[N],zong,ans[N],qe[N],tot; inline ll rd(){ ll x=0;char c=getchar();bool f=0; while(!isdigit(c)){if(c=='-')f=1;c=getchar();} while(isdigit(c)){ x=(x<<1)+(x<<3)+(c^48); c=getchar(); } return f?-x:x; } struct node{ ll val,num,day,x; bool operator <(const node &b)const{ return val>b.val; } }q[N]; int find(int x){return f[x]=f[x]==x?x:find(f[x]);} int main(){ n=rd();m=rd();k=rd(); for(int i=1;i<=n;++i){ a=rd();s=rd();c=rd();x=rd(); q[++tot]=node{a+s,1,x?((c-1)/x+1):1e5,0}; c--; if(c)q[++tot]=node{a,c,x?(c-1)/x+1:1e5,x}; } sort(q+1,q+tot+1); for(int i=1;i<=k;++i)qe[i]=rd(),md=max(md,qe[i]); for(int i=1;i<=md;++i)f[i]=i,tong[i]=m; for(int i=1;i<=tot;++i){ node now=q[i];cnt++;tag[cnt]=now.val; ll day=find(min(md,now.day));now.num-=(day-1)*now.x; while(now.num&&tong[day]){ int ss=min(tong[day],now.num); ji[cnt]+=ss;sum+=ss*now.val;tong[day]-=ss;now.num-=ss; if(!tong[day])f[day]=day-1; ll dd=day;day=find(day-1);dd-=day; now.num+=dd*now.x; } if(!find(md))break; } for(int i=1;i<=md;++i)sh[i]=sh[i-1]+tong[i],to[i]=to[i-1]+(m-tong[i]); for(int i=md;i>=1;--i)diss[i]=max(0ll,zong-sh[i]),zong+=(m-tong[i]); for(int i=md;i>=1;--i){ ans[i]=sum; ll tmp=diss[i-1]-diss[i]; while(tmp){ x=min(tmp,ji[cnt]); sum-=tag[cnt]*x; tmp-=x;ji[cnt]-=x; if(!ji[cnt]) cnt--; } } for(int i=1;i<=k;++i)printf("%lld ",ans[qe[i]]); return 0; }