P1072 光影八度交织官方题解

Gioush OJ · 光影八度交织 · 2026/09/07 00:00

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

当 $n,q\leq10$ 时，按照 $d_i$ 从大到小排序。固定一个前缀，表示只允许使用其中的光液。
再把前缀中的光液按照单位价格从小到大排序，依次购买最便宜的光液，判断是否能在预算内取得要求的总量。
枚举全部前缀即可得到答案。直接实现的时间复杂度为 $\mathcal O(qn^2\log n)$ 。

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

当 $n,q\leq300$ 时，可以预处理每个光影层次前缀中的价格顺序。询问时仍然枚举前缀，并取当前前缀内最便宜的 $r_j$ 个单位。
这一档揭示了判断前缀是否可行所需的两项信息：当前前缀能够提供的总量，以及其中最便宜若干单位的总费用。
后续不再改变可行性判断，只优化“得到一个前缀的最低费用”这一操作。

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

特殊性质 A 保证所有 $p_i=1$ 。只要可用总量不少于 $r_j$ ，最低费用就是 $r_j$ ，因此还需要检查 $r_j\leq g_j$ 。
按照 $d_i$ 从大到小扫描并累计容量，找到第一个容量不少于 $r_j$ 的前缀即可。
将询问按照需求排序后可以统一处理，时间复杂度为 $\mathcal O((n+q)\log n)$ 。

【部分分：测试点 13∼1613\sim 1613∼16】

特殊性质 B 保证每种光液至多使用一个单位，并且每次只需要一个单位。
此时只要 $p_i\leq g_j$ ，第 $i$ 种光液便可用于本次演出。在所有满足条件的光液中取最大的 $d_i$ 即可。
将光液按照价格排序并维护前缀最大层次，一次询问二分预算位置。时间复杂度为 $\mathcal O((n+q)\log n)$ 。

【部分分：测试点 17∼1917\sim 1917∼19】

对一次询问，按照光影层次从大到小加入光液，并在价格值域上维护容量与费用。
使用两棵树状数组分别维护各价格的可用数量和总费用。通过树状数组上的倍增找到取满 $r_j$ 个单位时经过的最后一个价格。
每次询问重新扫描全部光液，时间复杂度为 $\mathcal O(qn\log V)$ ，其中 $V=10^5$ 。正解需要让不同询问共享这些光影层次前缀。

【正解】

将所有光液按照 $d_i$ 从大到小排序。排序后的前 $k$ 种光液恰好是交织度至少为 $d_k$ 时可以使用的全部光液。
如果某个询问能由前 $k$ 种光液完成，那么加入更多光液后仍然能够完成，所以可行性关于前缀长度单调。
对每个询问二分最小的可行前缀。这个前缀对应的 $d_k$ 最大，也就是本次询问的答案。
固定一个前缀与询问 $(g,r)$ 。为了使费用最小，必须优先购买单位价格较低的光液。
在价格值域线段树的每个结点维护两项信息： $\operatorname{Num}$ 表示区间内的总容量， $\operatorname{Sum}$ 表示把这些容量全部买下的总费用。
判断前缀时先检查根结点的 $\operatorname{Num}\geq r$ 。容量不足时直接判为不可行，避免继续进行无意义的费用计算。
查询最便宜的 $r$ 个单位时，若左儿子的容量已经不少于 $r$ ，递归进入左儿子。
否则完整购买左儿子的全部容量，再到右儿子购买剩余部分。若已经到达单点价格 $p$ ，剩余费用就是 $pr$ 。
因此查询过程始终先取更低价格，返回值正是当前前缀取得 $r$ 个单位所需的最低费用。最低费用不超过 $g$ 时，当前前缀可行。
从前缀 $k-1$ 扩展到前缀 $k$ 时，只会修改价格 $p_k$ 对应的一条根到叶路径。复制这条路径便得到新的版本 $\operatorname{Root}_k$ 。
$\operatorname{Root}_k$ 保存前 $k$ 种光液的全部价格信息。二分过程中访问任意前缀时，直接使用对应版本即可。
交换论证说明固定前缀中选择最便宜的 $r$ 个单位最优，前缀单调性又保证二分得到最大交织度，因此算法正确。
设价格上界为 $V=10^5$ 。若先建立完整值域树，预处理复杂度为 $\mathcal O(V+n\log V)$ ；使用空根按需建立结点时可以写成 $\mathcal O(n\log V)$ 。
每次询问进行一次前缀二分，每次判断查询一次价格线段树，总时间复杂度为

\mathcal O\bigl(n\log V+q\log n\log V\bigr).

空间复杂度为 $\mathcal O(n\log V)$ 。容量、费用、预算与需求都需要使用 long long。

【参考代码】

1/*2Author:Ehundategh3Date:2026/8/204Name:blend.cpp5You steal,I kill.6*/7#include <cstdio>8#include <algorithm>9#define MAXN 10001010#define MAXV 10000011#define LSon Node[Now].LeftSon12#define RSon Node[Now].RightSon13using namespace std;14 15int c,T,n,q,cnt=0,Root[MAXN];16long long In1,In2;17 18struct juice{19    int d,p,l;20}J[MAXN];21 22struct node{23    int LeftSon,RightSon;24    long long Sum,Num;25}Node[MAXN<<5];26 27bool cmp(juice a,juice b){return a.d>b.d;}28 29int Modify(int Last,int l,int r,int Pos,int Num){30    int Now=++cnt;Node[Now]=Node[Last];31    Node[Now].Sum+=1ll*Pos*Num;Node[Now].Num+=Num;32    if(l==r) return Now;33    int Mid=(l+r)>>1;34    if(Pos<=Mid) LSon=Modify(Node[Last].LeftSon,l,Mid,Pos,Num);35    else RSon=Modify(Node[Last].RightSon,Mid+1,r,Pos,Num);36    return Now;37}38 39long long Query(int Now,int l,int r,long long Num){40    if(l==r) return 1ll*l*Num;41    int Mid=(l+r)>>1;42    if(Node[LSon].Num>=Num) return Query(LSon,l,Mid,Num);43    return Node[LSon].Sum+Query(RSon,Mid+1,r,Num-Node[LSon].Num);44}45 46bool Judge(int x,long long g,long long r){47    if(Node[Root[x]].Num<r) return false;48    return Query(Root[x],1,MAXV,r)<=g;49}50 51void Solve(){52    scanf("%d%d",&n,&q);53    cnt=0;Node[0]={0,0,0,0};Root[0]=0;54    for(int i=1;i<=n;i++) scanf("%d%d%d",&J[i].d,&J[i].p,&J[i].l);55    sort(J+1,J+n+1,cmp);56    for(int i=1;i<=n;i++) Root[i]=Modify(Root[i-1],1,MAXV,J[i].p,J[i].l);57    while(q-->0){58        scanf("%lld%lld",&In1,&In2);59        int Left=1,Right=n,Ans=-1;60        while(Left<=Right){61            int Mid=(Left+Right)>>1;62            if(Judge(Mid,In1,In2)) Ans=Mid,Right=Mid-1;63            else Left=Mid+1;64        }65        if(Ans==-1) puts("-1");66        else printf("%d\n",J[Ans].d);67    }68    return;69}70 71int main(){72    scanf("%d%d",&c,&T);73    while(T-->0) Solve();74    return 0;75}