考场上写了60分的二分答案，又写了15分的主席树，然后就弃了。。

合起来就A了啊！主席树忘了开20倍空间最后还炸掉了。

最水的签到题被我扔了，主要还是不会用线段树求前缀和。

做法应该是比较显然的，首先肯定要二分答案，然后需要查询的就是大于等于当前二分值的最便宜的L个饮料的总花费是否不超过g，这个直接上主席树就好。

1 #include
     
       2 #include
      
        3 #define rep(i,l,r) for (int i=l; i<=r; i++) 4 typedef long long ll; 5 using namespace std; 6  7 const int N=100010,M=1800010,Mx=100000; 8 struct P{ int d,p,l; }a[N]; 9 bool cmp(const P &a,const P &b){ return a.d
       
        >1;17     if (pos<=mid) ins(ls[y],ls[x],L,mid,pos,k);18         else ins(rs[y],rs[x],mid+1,R,pos,k);19     sz[x]=sz[ls[x]]+sz[rs[x]]; sm[x]=sm[ls[x]]+sm[rs[x]];20 }21 22 ll que(int x,int L,int R,ll pos){23     if (L==R) return L*pos;24     int mid=(L+R)>>1;25     if (sz[ls[x]]>=pos) return que(ls[x],L,mid,pos);26         else return sm[ls[x]]+que(rs[x],mid+1,R,pos-sz[ls[x]]);27 }28 29 bool jud(int mid){30     if (c[tot]-c[mid-1]
        
         =i; j--) ins(root[i],root[i],1,Mx,a[j].p,a[j].l);46     }47     rep(i,1,m){48         scanf("%lld%lld",&g,&q);49         int l=1,r=tot,ans=0;50         while (l<=r){51             int mid=(l+r)>>1;52             if (jud(mid)) ans=mid,l=mid+1; else r=mid-1;53         }54         printf("%d\n",b[ans]);55     }56     return 0;57 }