P1070 · OFFICIAL SOLUTION

P1070 晨汐散余香Ⅱ 官方题解

Gioush OJ · P1070 晨汐散余香Ⅱ

【Recall 晨汐散余香】

原题中每份香料只有一个单位，具有收益 $w_i$ 与失香时间 $t_i$ ，每天至多交易一份。询问只限制最多选择 $p$ 个交易日。
将香料按收益从大到小扫描，把当前香料放在不晚于 $t_i$ 的最晚空闲日。若不存在这样的日期，就舍弃当前香料。
依次成功放入的香料构成序列 $b_1,b_2,\ldots$ 。前 $r$ 份就是所有可行的 $r$ 份香料中收益最大的方案，因此记录收益前缀即可回答全部询问。

【Recall 正确性】

把当前香料安排到最晚空位不会占用更早的日期，所以不会使之后失香时间更早的香料更难加入。
固定一个收益下界，只看收益不低于它的香料。上述过程会选出其中数量最多的可行集合，否则可以把遗漏的香料加入并反复交换到更晚的位置，与当前香料无法放入矛盾。
因此前 $r$ 个成功单位的第 $r$ 大收益不会小于任意可行 $r$ 元方案的第 $r$ 大收益。对每个位置分别比较，便得到答案前缀的最优性。

【部分分：测试点 1∼41\sim 41∼4】

总库存不超过 $20$ 。可以枚举每个单位香料是否售出，再枚举或搜索这些香料被安排到哪些交易位置。
若某个单位被安排在失香时间之后，或者某一天使用了超过 $m$ 个交易位置，这个方案不合法。同一种香料首次售出时再加入一次初售赏金。
时间复杂度为指数级。这一档已经完整保留了截止时间、每日容量和只出现一次的额外收益。

【部分分：测试点 5∼85\sim 85∼8】

先推广每天的交易次数。把第 $d$ 天拆成编号为 $m(d-1)+1\sim md$ 的 $m$ 个位置，那么在第 $d$ 天失香的单位，其截止位置就是 $md$ 。
再将每种香料展开成 $c_i$ 个单位。若 $x_i>0$ ，第 $r$ 个单位的失香时间为 $\lceil r/x_i\rceil$ ；若 $x_i=0$ ，它在当前询问内始终有效。
展开以后，每个单位仍然只有“收益”和“截止位置”两个属性，这已经与 Recall 中的问题完全相同。
还需要处理初售赏金。对第 $i$ 种香料，取失香时间最晚的一个单位，把它的收益设为 $a_i+s_i$ ，其余单位的收益均设为 $a_i$ 。
若某个方案售出了这种香料，却没有售出这个单位，就用它替换任意一个已经售出的同类单位。收益不变，截止时间只会变晚，所以方案仍然合法。
于是初售赏金也被转化成了一个普通单位的收益。对每次询问重新运行 Recall 中的贪心，设总库存为 $s$ ，时间复杂度为 $\mathcal O(qs\log s)$ 。

【部分分：测试点 9∼129\sim 129∼12】

令 $P=\max p_j$ ，只对前 $P$ 天建立 $mP$ 个位置，并运行一次推广后的贪心。每成功放入一个单位，就记录当前收益前缀。
对询问 $p$ ，只需要前 $mp$ 个成功单位。它们原本已经能够合法安排，把所占位置依次向左压缩后，一定可以全部放入前 $mp$ 个位置。
因此询问仍然只是读取一个答案前缀。时间复杂度为 $\mathcal O(s\log s+q)$ ，与原题相比仅仅把可用位置数从 $p$ 改成了 $mp$ 。

【部分分：测试点 13∼1513\sim 1513∼15】

这一档中 $mP\leq3\times10^3$ 。无论库存有多大，答案中真正能够出现的单位都不会超过 $mP$ 个，所以没有必要展开其余单位。
同一种香料的普通单位收益均为 $a_i$ ，并且可以按照失香时间分成若干批。我们只记录当前失香时间最晚的一批，整批处理完成后再生成前一批。
用优先队列维护各香料当前能够生成的最高收益，用并查集寻找最晚空位。这样恰好是在不改变 Recall 贪心顺序的前提下，延迟生成它真正访问到的单位。

【部分分：测试点 16∼1916\sim 1916∼19】

特殊性质保证所有 $x_i=0$ ，所以全部单位都可以在任意交易日售出，不再需要处理截止位置。
每种香料提供一个收益为 $a_i+s_i$ 的单位，以及至多 $c_i-1$ 个收益为 $a_i$ 的单位。把这些带数量的收益段从大到小排序并求前缀即可。
时间复杂度为 $\mathcal O(n\log n+q\log n)$ 。这一档说明普通单位可以整批保存，完整数据只需要为每一批重新带上截止位置。

【正解】

令 $P=\max p_j$ 。一天拆成 $m$ 个位置后，截止第 $d$ 天对应的位置上界为 $md$ ，我们只需要维护前 $mP$ 个位置。
若 $x_i>0$ ，第 $i$ 种香料在询问范围内的最晚截止日为

D_i=\min\left(P,\left\lceil\frac{c_i}{x_i}\right\rceil\right).

当 $x_i=0$ 时，令 $D_i=P$ 。

先生成一个截止日为 $D_i$ 、收益为 $a_i+s_i$ 的单位。自然截止日超过 $P$ 的普通单位合并到第 $P$ 天，其余普通单位按照相同截止日组成批次。
优先队列中只保存每种香料当前应该处理的单位或批次，并按照收益从大到小取出。初售单位的收益不小于同类普通单位，所以尚未生成的单位不可能越过它提前出现。
对截止日为 $d$ 的单位，用并查集查询不超过 $md$ 的最晚空位。占用位置 $r$ 后，将它指向 $r-1$ 左侧最近的空位，这与 Recall 中的实现完全相同。
当前批次全部放入后，才生成这种香料截止时间更早的下一批。这样优先队列始终给出了逐单位展开后，下一个应该被贪心扫描的收益。
若一个批次只能放入一部分，最终一定是因为不超过其截止位置的空位已经全部占满。后续同类批次的截止时间只会更早，所以它们也不可能再被放入。
每成功放入一个单位，就记录一次收益前缀。设最终成功放入 $C$ 个单位，询问 $p_j$ 的答案就是前 $\min(mp_j,C)$ 项收益之和。
到这里，算法仍然是 aroma 的“收益降序、占用最晚空位、记录答案前缀”，只是用批次与优先队列避免了完整展开库存。
优先队列初始加入 $n$ 个初售单位，之后至多有 $mP$ 个单位真正占用交易位置，因此总处理规模为 $\mathcal O(n+mP)$ 。
令 $P=\max p_j$ 。总时间复杂度为 $\mathcal O((n+mP)\log n+q)$ ，空间复杂度为 $\mathcal O(n+mP)$ 。
收益前缀可能达到 $10^{15}$ 量级，需要使用 long long。多组数据之间还要清空优先队列，并重新初始化前 $mP$ 个并查集位置。

【参考代码】

1/*2Author:Ehundategh3Date:2026/8/194Name:scent.cpp5You steal,I kill.6*/7#include <queue>8#include <vector>9#include <cstdio>10#include <cstring>11#include <algorithm>12#define MAXN 10001013#define MAXS 100001014using namespace std;15 16int c,T,n,m,q,Fa[MAXS],Ask[MAXN];17long long Pref[MAXS];18 19int Find(int x) {20    int y=x;21    while (Fa[y]!=y) y=Fa[y];22    while (Fa[x]!=x) {23        int Temp=Fa[x];24        Fa[x]=y;25        x=Temp;26    }27    return y;28}29 30struct type{31    long long a,s,c,x,Count,Remain;32    int Day,MaxDay;33    bool Bonus;34    void Init(int p) {35        MaxDay=p;36        Bonus=true;37        Day=x==0?p:(int)min<long long>(p,(c+x-1)/x);38        Count=1;39        Remain=c-1;40    }41    bool Next() {42        if (Bonus) {43            Bonus=false;44            if (!Remain||!MaxDay) return false;45            if (!x) {46                Day=MaxDay;47                Count=Remain;48                return true;49            }50            long long Last=(c+x-1)/x;51            if (Last>=MaxDay) {52                Day=MaxDay;53                Count=c-x*(MaxDay-1)-1;54            }55            else {56                Day=(int)Last;57                Count=c-x*(Last-1)-1;58            }59            if (Count>0) return true;60        }61        else {62            Remain-=Count;63            if (!Remain||!x) return false;64            Day--;65            Count=min(x,Remain);66            return Day>0;67        }68        while (Remain>0&&Day>1) {69            Day--;70            Count=min(x,Remain);71            if (Count>0) return true;72        }73        return false;74    }75    long long Get(){return a+(Bonus?s:0);}76}A[MAXN];77 78struct node{79    long long Value;80    int Id;81    bool operator <(const node &Other)const{82        if (Value!=Other.Value) return Value<Other.Value;83        return Id>Other.Id;84    }85};86 87priority_queue <node> Q;88 89void Solve() {90    scanf("%d%d%d",&n,&m,&q);91    for (int i=1;i<=n;i++) scanf("%lld%lld%lld%lld",&A[i].a,&A[i].s,&A[i].c,&A[i].x);92    int MaxP=0;93    for (int i=1;i<=q;i++) {94        scanf("%d",&Ask[i]);95        MaxP=max(MaxP,Ask[i]);96    }97    int Capacity=m*MaxP,Count=0;98    for (int i=0;i<=Capacity;i++) Fa[i]=i;99    while (!Q.empty()) Q.pop();100    Pref[0]=0;101    for (int i=1;i<=n;i++) {102        A[i].Init(MaxP);103        Q.push({A[i].Get(),i});104    }105    while (!Q.empty()&&Count<Capacity) {106        node Temp=Q.top();Q.pop();107        type &Now=A[Temp.Id];108        int Limit=m*Now.Day;109        long long Used=0;110        while (Used<Now.Count) {111            int Pos=Find(Limit);112            if (!Pos) break;113            Fa[Pos]=Find(Pos-1);114            Count++;115            Pref[Count]=Pref[Count-1]+Temp.Value;116            Used++;117            if (Count==Capacity) break;118        }119        if (Used==Now.Count&&Now.Next()) Q.push({Now.Get(),Temp.Id});120    }121    for (int i=1;i<=q;i++) {122        int Take=min(m*Ask[i],Count);123        printf("%lld\n",Pref[Take]);124    }125    return;126}127 128int main() {129    scanf("%d%d",&c,&T);130    while (T-->0) Solve();131    return 0;132}