P4602 [CTSC2018] 混合果汁 题解

题目链接：P4602 [CTSC2018] 混合果汁

较为简单的一题，模拟赛场切了，不考虑整体二分这个知识点的难度可能是下位蓝

考虑整体二分，按照 $ d_i $ 排序，然后每次处理只有右区间的果汁，先把小朋友按照 $ L_j $ 排序，然后把右区间的果汁按照 $ p_i $ 排序，双指针即可。

然后这显然是错的，因为没有考虑到可能是左区间的右区间，因此还要加上前面层如果是左区间 右区间的值，考虑开一棵权值线段树，位置 $ i $ 存价格为 $ i $ 的果汁的升数之和，然后查询时即查询对于 $ L_j $ 升需要的最少钱数是多少，直接线段树上二分即可，上面处理右区间的流程也可以简化到这里面。

代码：

#include<bits/stdc++.h>
#define time(null) chrono::steady_clock::now().time_since_epoch().count()
#define int long long
#define uint unsigned long long
#define debug() cout<<"come here\n"
#define INF 0x3f3f3f3f3f3f3f3f
#define pii pair<int,int>
#define pb push_back
#define Code return
#define by 0
#define MCYYDS ;
using namespace std;
int qpow(int a,int b,int p=INF){int ret=1;while(b){if(b&1)ret=(ret*a)%p;a=(a*a)%p;b>>=1;}return ret;}
inline int read(){int ret=0,f=1;char ch=getchar();while(ch<'0'||ch>'9')f=(ch=='-'?-1:f),ch=getchar();while(ch>='0'&&ch<='9')ret=(ret<<3)+(ret<<1)+(ch^48),ch=getchar();return ret*f;}
inline void write(int x){if(x<0){putchar('-');write(-x);return ;}if(x>9)write(x/10);putchar((char)(x%10+48));}
inline void writech(int x,char ch){write(x);putchar(ch);}
struct node{int d,p,l;
};
struct ask{int g,l,id;
};
bool cmpb(ask x,ask y)
{return x.l<y.l;
}
bool cmp(node x,node y)
{return x.d<y.d;
}
bool cmpa(node x,node y)
{return x.p<y.p;
}
vector<int> ans;
struct tree{int l,r,cnt,sum;
}tree[400005];
void update(int l,int r,int id,int p,int v)
{if(l==r){tree[id].cnt+=v;tree[id].sum+=v*p;return ;}int mid=l+r>>1;if(p<=mid)update(l,mid,id<<1,p,v);else update(mid+1,r,id<<1|1,p,v);tree[id].cnt=tree[id<<1].cnt+tree[id<<1|1].cnt;tree[id].sum=tree[id<<1].sum+tree[id<<1|1].sum;return ;
}
int query(int l,int r,int id,int x)
{if(l==r)return l*x;int mid=l+r>>1;if(tree[id<<1].cnt>=x)return query(l,mid,id<<1,x);return tree[id<<1].sum+query(mid+1,r,id<<1|1,x-tree[id<<1].cnt);
}
void dfs(int l,int r,vector<node> a,vector<ask> b)
{if(l==r){for(auto x:b){ans[x.id]=a[0].d;}return ; }int mid=l+r>>1;sort(a.begin(),a.end(),cmp);vector<node> al,ar;for(int i=l;i<=mid;i++){al.pb(a[i-l]);}for(int i=mid+1;i<=r;i++){ar.pb(a[i-l]);}sort(ar.begin(),ar.end(),cmpa);vector<ask> bl,br;for(auto x:ar){
//		cout<<x.p<<' '<<x.l<<'\n';update(1,100000,1,x.p,x.l);}for(auto x:b){
//		cout<<x.l<<' '<<x.g<<' '<<l<<' '<<r<<' '<<query(1,100000,1,x.l)<<'\n';if(tree[1].cnt>=x.l&&query(1,100000,1,x.l)<=x.g)br.pb(x);else bl.pb(x);}dfs(l,mid,al,bl);for(auto x:ar){update(1,100000,1,x.p,-x.l);}dfs(mid+1,r,ar,br);
}
signed main()
{
//	ios::sync_with_stdio(0);
//	cin.tie(0);
//	cout.tie(0);int n=read(),m=read();vector<node> a(n+1);ans.assign(m,-1);a[0].d=-1;a[0].p=0;a[0].l=INF;for(int i=1;i<=n;i++){a[i].d=read();a[i].p=read();a[i].l=read();}vector<ask> b(m);for(int i=0;i<m;i++){b[i].g=read(),b[i].l=read();b[i].id=i;}sort(b.begin(),b.end(),cmpb);dfs(0,n,a,b);for(auto x:ans){writech(x,'\n');}Code by MCYYDS
}