I智乃挖坑（二分答案+二重差分）
显然，对于这个问题，越挖到最后越可能挖出边界。答案具有单调性。
对挖出边界需要的挖坑次数二分，对二分到的mid进行check
二重差分：
在区间[l, r]上，加首项为a，公差为d的等差数列，等效于在一重差分和二重差分上做如下操作。
差分还原为原数组：“二重差分的
展开全文
https://ac.nowcoder.com/acm/contest/120565/I
（不管怎么样数据结构还是没有白学）
非常暴力的做法。
注意到一次操作可以看着的差分序列，显然可以用区间修改的线段树维护。于是问题转化成：每次操作后，是否存在一个位置，的前缀和。
那么我们可以很快得到一组数据的答
展开全文
注：此题解参考@FZANOTFOUND这位大佬的题解，下面是个人学习了之后的理解
二分答案需要挖的次数，在check函数中，计算挖mid次是否会挖出地图边界，开两个数组a和b，分别是系数和常数，每次挖，用差分的方法，把坑分为左半边和右半边，在坑的开始加一（用a数组记录），坑的结束减一(右半边在开始的
展开全文
I题 | 智乃挖坑
解题思路：
答案具有单调性，因此可以二分答案。已知挖的坑都是三角形，因此可以对差分数组求两次前缀和来构建这种三角形。每次操作复杂度都是 ，每次 的复杂度是 。
关于对差分数组求两次前缀和后的部分性质见下图（重点看 diff 和 pre2）：
示例代码：
int n
展开全文
-
扫描二维码，关注牛客
- 意见反馈
-
下载牛客APP，随时随地刷题
- 牛客竞赛，专业的竞技算法训练平台
-
扫描二维码，进入QQ群
扫码关注“比赛自动姬”
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备 11010502036488号
