第一次写可持久化线段树，可以很明显的想到二分一个美味度，因为很明显此题具有单调性。
然后就可以随便乱搞了，按照美味度排序，然后按照每升价格建一个可持久化线段树，然后主要是check函数
当我们要判断一个美味度是否可行的时候，我们先可以将其下标得到，然后贪心去先选择价格最小的，然后就是个模拟了
复杂度:$O(m log^2 n)$
#include<iostream> #include<cstring> #include<cstdio> #include<algorithm> #define int long long using namespace std; inline int read(){ int f=1,ans=0;char c=getchar(); while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){ans=ans*10+c-'0';c=getchar();} return f*ans; } const int MAXN=100001; const int M=100001; struct node{ int d,p,l; }x[MAXN]; bool cmp(node x1,node x2){ if(x1.d==x2.d) return x1.p<x2.p; return x1.d<x2.d; } int ls[MAXN*20],cnt,rs[MAXN*20],tr[MAXN*20],ts[MAXN*20],tw[MAXN*20],n,T; void update(int &rt,int las,int l,int r,int X,int ss,int ww){ rt=++cnt;ls[rt]=ls[las],rs[rt]=rs[las],ts[rt]=ts[las]+ss,tw[rt]=tw[las]+ww; if(l==r) return; int mid=l+r>>1; if(X<=mid) update(ls[rt],ls[las],l,mid,X,ss,ww); else update(rs[rt],rs[las],mid+1,r,X,ss,ww); return; } int l,r,maxn,limw,lims; int query(int rt,int l,int r,int W){ if(l==r) return W*l; int mid=l+r>>1; if(ts[ls[rt]]>=W) return query(ls[rt],l,mid,W); else return tw[ls[rt]]+query(rs[rt],mid+1,r,W-ts[ls[rt]]); } bool check(int xx){ if(lims>limw)return 0; if(ts[tr[xx]]>=lims&&query(tr[xx],1,M,lims)<=limw) return 1; return 0; } signed main(){ n=read(),T=read(); for(int i=1;i<=n;i++) x[i].d=read(),x[i].p=read(),x[i].l=read();x[0].d=-1; sort(x+1,x+n+1,cmp); for(int i=n;i>=1;i--) update(tr[i],tr[i+1],1,M,x[i].p,x[i].l,x[i].p*x[i].l); while(T--){ limw=read(),lims=read(); maxn=0,l=1,r=n; while(l<=r){ int mid=l+r>>1; if(check(mid)) maxn=max(maxn,mid),l=mid+1; else r=mid-1; } printf("%d ",x[maxn].d); } return 0; }