RainAir
My OI Blog
RainAir
「BZOJ5028」小Z的加油店

题目描述

题目链接
小Z经营一家加油店。小Z加油的方式非常奇怪。他有一排瓶子,每个瓶子有一个容量vi。每次别人来加油,他会让
别人选连续一段的瓶子。他可以用这些瓶子装汽油,但他只有三种操作:
1. 把一个瓶子完全加满;
2. 把一个瓶子完全倒空;
3. 把一个瓶子里的汽油倒进另一个瓶子,直到倒出瓶子空了或者倒进的瓶子满了。
当然,为了回馈用户,小Z会时不时选择连续一段瓶子,给每个瓶子容积都增加x。
为了尽可能给更多的人加油,每次客户来加油他都想知道他能够倒腾出的汽油量最少是多少?
当然他不会一点汽油都不给客户。

解题报告

首先考虑只有询问怎么做。
一个显然的结论是:能表示出来的最小的数字一定是这些数字的gcd。
所以只有询问的话倍增处理一下gcd就可以了,时间复杂度 $O(nlog^2n)$
然后考虑加入了修改怎么做。
如果只有单点修改还是比较好做的,用线段树维护一下区间gcd,每次修改和查询都是 $O(log^2n)$ 的,总复杂度 $O(nlog^2n)$。
但是这里要求是区间修改,怎么办呢?
我们考虑将这个区间修改变成单点修改可以解决的问题,注意到 $\text{gcd}(a,b) = \text{gcd}(b,a-b)$,所以区间 $[l,r]$ 的 gcd 等价于将这个区间差分后的 gcd。
于是我们用线段树维护一下差分后的数组的区间 gcd 和区间和,支持单点修改和区间查询即可。
时间复杂度 $O(nlog^2n)$

代码

赞赏
知识共享许可协议
本文链接: https://blog.aor.sd.cn/archives/308
如文中无特殊声明,本文采用 CC BY-NC-SA 4.0 进行许可,转载请说明出处!
希望 CSP 不要翻车,希望省选不要翻车
https://secure.gravatar.com/avatar/97c17c68a1e55e11bb5558bc0f10cc0d?s=256&d=mm&r=g

RainAir

文章作者

一个OIer。

发表评论

textsms
account_circle
email

RainAir

「BZOJ5028」小Z的加油店
题目描述 题目链接 小Z经营一家加油店。小Z加油的方式非常奇怪。他有一排瓶子,每个瓶子有一个容量vi。每次别人来加油,他会让 别人选连续一段的瓶子。他可以用这些瓶子装汽油,但他只有…
扫描二维码继续阅读
2018-11-24
标签
近期评论