CTSC2018 Day2T1 Juice混合果汁

【题解】

　　在考场上A掉的题。

　　把美味度排个序，然后按照价格p为权值建立主席树，把每个果汁按照拍好的顺序添加进去。主席树上维护总升数cnt以及总价格sum。对于每个询问，我们二分一个美味值，check的时候去主席树上查找大于等于这个美味值的果汁中购买L升的价格即可。

 #include<cstdio>
 #include<algorithm>
 #define LL long long
 #define rg register
 #define N 100010
 #define ls (a[u].l)
 #define rs (a[u].r)
 using namespace std;
 int n,m,n2,tot,rt[N];
 LL cnt,sum,G,L;
 struct rec{
     int d,p,l;
 }jui[N];
 struct tree{
     LL cnt,sum; int l,r;
 }a[];
 inline LL read(){
     LL k=; int f=; char c=getchar();
     while(c<''||c>'')c=='-'&&(f=-),c=getchar();
     while(''<=c&&c<='')k=k*+c-'',c=getchar();
     return k*f;
 }
 inline bool cmp(rec a,rec b){return a.d>b.d;}
 void add(int &u,int l,int r,int pos){
     a[++tot]=a[u]; a[u=tot].cnt+=cnt; a[u].sum+=sum;
     int mid=(l+r)>>;
     if(l<r)
         if(pos<=mid) add(ls,l,mid,pos);
         else add(rs,mid+,r,pos);
 }
 LL query(int u,int l,int r,LL k){
     if(l==r) return a[u].cnt<k?G+:k*l;
     int mid=(l+r)>>;
     if(a[ls].cnt>=k) return query(ls,l,mid,k);
     else return query(rs,mid+,r,k-a[ls].cnt)+a[ls].sum;
 }
 int main(){
     n=read(); m=read();
     for(rg int i=;i<=n;i++){
         jui[i].d=read(); jui[i].p=read(); jui[i].l=read();
         n2=max(n2,jui[i].p);
     }
     sort(jui+,jui++n,cmp);
     for(rg int i=;i<=n;i++){
         cnt=jui[i].l; sum=1ll*cnt*jui[i].p;
         add(rt[i]=rt[i-],,n2,jui[i].p);
     }
     while(m--){
         G=read(); L=read();
         int l=,r=n+;
         while(l+<r){
             int mid=(l+r)>>;
             if(query(rt[mid],,n2,L)>G) l=mid;
             else r=mid;
         }
         printf("%d\n",r<=n?jui[r].d:-);
     }
     return ;
 }