[CTSC2018]混合果汁

题目连接：https://www.luogu.org/problemnew/show/P4602

因为题中说是让最小值最大，所以自然想到二分答案。对于每一个二分的值，判断是否合法，若合法，在右区间二分，否则在左区间二分。

那么如何判断是否合法呢？首先，对于每一个二分值mid，我们应该在[mid, n]的区间中贪心的取价格尽量低的果汁，当该小朋友所有的钱花光后，判断取到的果汁是否到了Lj升。

至于如何取，首先因为价格是无序的，所以可以建立一个大小为价格的值域的线段树，同时维护每一个区间的价格之和以及对应多少升之和（原谅我这小学水平的语文）。又因为是在动区间查询，线段树无法胜任，所以就想到了主席树（想想板子题区间第k小）。

 #include<cstdio>

 #include<iostream>

 #include<cstring>

 #include<cmath>

 #include<algorithm>

 #include<cctype>

 using namespace std;

 #define enter printf("\n")

 #define space printf(" ")

 typedef long long ll;

 const int INF = 0x3f3f3f3f;

 const int maxn = 1e5 + ;

 const int max_size = 2e6 + ;

 const int Max = 1e5;

 inline ll read()

 {

     ll ans = ;

     char ch = getchar(), last = ' ';

     while(!isdigit(ch)) {last = ch; ch = getchar();}

     while(isdigit(ch))

     {

         ans = ans *  + ch - ''; ch = getchar();

     }

     if(last == '-') ans = -ans;

     return ans;

 }

 inline void write(ll x)

 {

     if(x < ) x = -x, putchar('-');

     if(x >= ) write(x / );

     putchar('' + x % );

 }

 int n, m;

 struct Juice

 {

     int d, p, l;

     bool operator < (const Juice& other)const        //按d排序

     {

         return d < other.d;

     }

 }a[maxn];

 int tot = , root[max_size], lson[max_size], rson[max_size];

 ll sum_co[max_size], sum_lit[max_size];        //sun_co[]:当前区间全买所花的钱，sum_lit[]当前区间有多少升

 void update(int old, int& now, int L, int R, int p, int v)

 {

     now = ++tot;

     lson[now] = lson[old]; rson[now] = rson[old];

     sum_co[now]    = sum_co[old] + (ll)p * v;

     sum_lit[now] = sum_lit[old] + v;

     if(L == R) return;

     int mid = (L + R) >> ;

     if(p <= mid) update(lson[old], lson[now], L, mid, p, v);

     else update(rson[old], rson[now], mid + , R, p, v);

 }

 ll query(int old, int now, int L, int R, ll p)

 {

     if(L == R) return min(p / L, sum_lit[now] - sum_lit[old]);            //判断当前剩的钱是否够买这种果汁的所有容量，否则只买一部分

     ll sum_cost = sum_co[lson[now]] - sum_co[lson[old]];                //判断是否能买做区间的所有东西

     int mid = (L + R) >> ;

     if(p <= sum_cost) return query(lson[old], lson[now], L, mid, p);

     else return sum_lit[lson[now]] - sum_lit[lson[old]] + query(rson[old], rson[now], mid + , R, p - sum_cost);        //说明能买这些东西了，在右子区间查找

 }

 ll GG, LL;

 bool judge(int x)        //钱数为下标，判断能买到的果汁有多少升

 {

     return query(root[x - ], root[n], , Max, GG) >= LL;

 }

 int solve()

 {

     int L = , R = n;

     if(GG < LL) return -;

     while(L < R)

     {

         int mid = (L + R + ) >> ;

         if(judge(mid)) L = mid;        //注意是L = mid,而不是L = mid +1，因为mid是当前合法的条件，不能舍去

         else R = mid - ;

     }

     return !L ? - : a[L].d;            //如果一直不合法，那么就会一直往做区间找，所以无法满足就是一直找到0

 }

 int main()

 {

     n = read(); m = read();

     for(int i = ; i <= n; ++i) {a[i].d = read(); a[i].p = read(); a[i].l = read();}

     sort(a + , a + n + );

     for(int i = ; i <= n; ++i) update(root[i - ], root[i], , Max, a[i].p, a[i].l);

     for(int i = ; i <= m; ++i)

     {

         GG = read(), LL = read();

         write(solve()); enter;

     }

     return ;

 }