2019.01.14 bzoj5343: [Ctsc2018]混合果汁(整体二分+权值线段树)

时间:2021-12-29 01:31:19

传送门

整体二分好题。

题意简述:nnn种果汁,每种有三个属性:美味度,单位体积价格,购买体积上限。

现在有mmm个询问,每次问能否混合出总体积大于某个值,总价格小于某个值的果汁,如果能,求所有方案中用于混合的果汁的美味度的最小值的最大值。


思路:

首先考虑单次询问怎么做,看这个询问的类型应该可以二分答案。

接着思考如何checkcheckcheck,这个时候可以发现果汁可以按照美味度单调递减排列来让我们二分这个答案。

拍完序之后就可以采用贪心的方式,我们知道应该从单位体积从小到大买,因此我们建一棵权值线段树在上面二分寻找如果要满足购买那么多体积需要的最小花费,然后跟允许的花费比较进行下一次二分。

可以观察到对于所有的询问这样的操作形式都是一模一样的,因此我们整体二分即可。

一个判无解的小技巧:加入一种美味度为-1,单位体积价格为0,购买上限为inf*的饮料,这样无解的自然会二分到这个点上

代码:

#include<bits/stdc++.h>
#define lc (p<<1)
#define rc (p<<1|1)
#define mid (l+r>>1)
#define ri register int
using namespace std;
typedef long long ll;
inline ll read(){
	ll ans=0;
	char ch=getchar();
	while(!isdigit(ch))ch=getchar();
	while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
	return ans;
}
const int N=1e5+5,mx=100000;
int n,m,ans[N],cur=0;
ll s1[N<<2],s2[N<<2];
struct Upd{int d,p,l;}a[N];
struct Q{int id;ll g,l;}qry[N],t1[N],t2[N];
inline void pushup(int p){s1[p]=s1[lc]+s1[rc],s2[p]=s2[lc]+s2[rc];}
inline void update(int p,int l,int r,int k,int v){
	if(l==r){s1[p]+=v,s2[p]+=(ll)v*l;return;}
	if(k<=mid)update(lc,l,mid,k,v);
	else update(rc,mid+1,r,k,v);
	pushup(p);
}
inline ll query(int p,int l,int r,int v){
	if(!v)return 0;
	if(l==r)return (ll)v*l;
	if(s1[lc]>=v)return query(lc,l,mid,v);
	return s2[lc]+query(rc,mid+1,r,v-s1[lc]);
}
inline bool cmp(const Upd&a,const Upd&b){return a.d>b.d;}
inline void solve(int ql,int qr,int l,int r){
	if(ql>qr||l>r)return;
	if(l==r){for(ri i=ql;i<=qr;++i)ans[qry[i].id]=a[l].d;return;}
	int hd1=0,hd2=0;
	while(cur<mid)++cur,update(1,1,mx,a[cur].p,a[cur].l);
	while(cur>mid)update(1,1,mx,a[cur].p,-a[cur].l),--cur;
	for(ri i=ql;i<=qr;++i){
		if(qry[i].l>s1[1])t2[++hd2]=qry[i];
		else if(query(1,1,mx,qry[i].l)<=qry[i].g)t1[++hd1]=qry[i];
		else t2[++hd2]=qry[i];
	}
	for(ri i=1;i<=hd1;++i)qry[ql+i-1]=t1[i];
	for(ri i=1;i<=hd2;++i)qry[ql+hd1+i-1]=t2[i];
	solve(ql,ql+hd1-1,l,mid),solve(ql+hd1,qr,mid+1,r);
}
int main(){
	n=read(),m=read();
	for(ri i=1;i<=n;++i)a[i].d=read(),a[i].p=read(),a[i].l=read();
	a[++n]=(Upd){-1,0,0x3f3f3f3f};
	sort(a+1,a+n+1,cmp);
	for(ri i=1;i<=m;++i)qry[i].id=i,qry[i].g=read(),qry[i].l=read();
	solve(1,m,1,n);
	for(ri i=1;i<=m;++i)cout<<ans[i]<<'\n';
	return 0;
}

2019.01.14 bzoj5343: [Ctsc2018]混合果汁(整体二分+权值线段树)的更多相关文章

  1. P5163 WD与地图(整体二分&plus;权值线段树)

    传送门 细节要人命.jpg 这题思路太新奇了--首先不难发现可以倒着做变成加边,但是它还需要我们资瓷加边的同时维护强连通分量.显然加边之后暴力跑是不行的 然后有一个想法,对于一条边\((u,v)\), ...

  2. &lbrack;bzoj5343&rsqb;&lbrack;Ctsc2018&rsqb;混合果汁&lowbar;二分答案&lowbar;主席树

    混合果汁 bzoj-5343 Ctsc-2018 题目大意:给定$n$中果汁,第$i$种果汁的美味度为$d_i$,每升价格为$p_i$,每次最多添加$l_i$升.现在要求用这$n$中果汁调配出$m$杯 ...

  3. HDU6621 K-th Closest Distance 第 k 小绝对值(主席树(统计范围的数有多少个)&plus; 二分 &vert;&vert; 权值线段树&plus;二分)

    题意:给一个数组,每次给 l ,r, p, k,问区间 [l, r] 的数与 p 作差的绝对值的第 k 小,这个绝对值是多少 分析:首先我们先分析单次查询怎么做: 题目给出的数据与多次查询已经在提示着 ...

  4. 2019杭电多校第三场hdu6606 Distribution of books&lpar;二分答案&plus;dp&plus;权值线段树&rpar;

    Distribution of books 题目传送门 解题思路 求最大值的最小值,可以想到用二分答案. 对于二分出的每个mid,要找到是否存在前缀可以份为小于等于mid的k份.先求出这n个数的前缀和 ...

  5. 2019年CCPC网络赛 HDU 6703 array【权值线段树】

    题目大意:给出一个n个元素的数组A,A中所有元素都是不重复的[1,n].有两种操作:1.将pos位置的元素+1e72.查询不属于[1,r]中的最小的>=k的值.强制在线. 题解因为数组中的值唯一 ...

  6. The Stream of Corning 2&lpar; 权值线段树&sol;&lpar;树状数组&plus;二分&rpar; &rpar;

    题意: 有两种操作:1.在[l,r]上插入一条值为val的线段 2.问p位置上值第k小的线段的值(是否存在) 特别的,询问的时候l和p合起来是一个递增序列 1<=l,r<=1e9:1&lt ...

  7. BZOJ5343 &lbrack;Ctsc2018&rsqb;混合果汁 【二分 &plus; 主席树】

    题目链接 BZOJ5343 题解 明显要二分一下美味度,然后用尽量少的价格去购买饮料,看看能否买到\(L\)升,然后看看能否控制价格在\(g\)内 尽量少的价格,就优先先选完便宜的饮料,由于询问的是一 ...

  8. 【XSY2720】区间第k小 整体二分 可持久化线段树

    题目描述 给你你个序列,每次求区间第\(k\)小的数. 本题中,如果一个数在询问区间中出现了超过\(w\)次,那么就把这个数视为\(n\). 强制在线. \(n\leq 100000,a_i<n ...

  9. 【BZOJ3110】K大数查询(权值线段树套线段树&plus;标记永久化,整体二分)

    题意:有N个位置,M个操作.操作有两种,每次操作 如果是1 a b c的形式表示在第a个位置到第b个位置,每个位置加入一个数c 如果是2 a b c形式,表示询问从第a个位置到第b个位置,第C大的数是 ...

随机推荐

  1. Spring预处理

    当需要在某些Spring项目一启动,就执行某些操作时,需要实现改接口ApplicationListener,重写onApplicationEvent方法,将需要的预处理操作全部写在该方法中 当初始化完 ...

  2. Html标签第一课

    <p>段落标签</p> <h1>字体标签,1到6,越来越小</h1>.....<h6></h6><h>标签自动换行 ...

  3. Thymeleaf 集成spring

    Thymeleaf 集成spring 如需先了解Thymeleaf的单独使用,请参考<Thymeleaf模板引擎使用>一文. 依赖的jar包 Thymeleaf 已经集成了spring的3 ...

  4. &dollar;&period;ajax用法与举例

    下面是一段比较常用到的 $.ajax 方法: $.ajax({ type:'GET', url:'http://www.phpernote.com/jquery.php', data:{usernam ...

  5. WSGI

    [WSGI] WSGI:Web Server Gateway Interface. WSGI接口定义非常简单,它只要求Web开发者实现一个函数,就可以响应HTTP请求.我们来看一个最简单的Web版本的 ...

  6. SQL删除重复的记录&lpar;只保留一条&rpar;

    首先新建表: --创建示例表 CREATE TABLE t ( id ,) PRIMARY KEY, a ), b ) ) --插入数据 INSERT INTO t SELECT 'aa','bb' ...

  7. j2ee servlet listener

    JSP/Servlet 中的事件处理写过AWT或Swing程序的人一定对桌面程序的事件处理机制印象深刻:通过实现Listener接口的类可以在特定事件(Event)发生时,呼叫特定的方法来对事件进行响 ...

  8. HDU 2064 汉诺塔III&lpar;递归&rpar;

    题目链接 Problem Description 约19世纪末,在欧州的商店中出售一种智力玩具,在一块铜板上有三根杆,最左边的杆上自上而下.由小到大顺序串着由64个圆盘构成的塔.目的是将最左边杆上的盘 ...

  9. WinForm 制作一个简单的计算器

    namespace WindowsFormsApplication6 { public partial class Form1 : Form { //存储上次点击了什么按钮,0代表什么都没有点击,1代 ...

  10. SQL语句更新时间字段的年份、月份、天数、时、分、秒

    SQL语句更新时间字段的年份.月份.天数.时.分.秒 --修改d表日期字段的年份update dset birth=STUFF(convert(nvarchar(23),birth,120),1,4, ...