首页 > 小阳的贝壳
开通博客写题解
头像 11D_Beyonder
发表于 2020-05-29 16:11:26
题目描述 小阳手中一共有 个贝壳，每个贝壳都有颜色，且初始第 个贝壳的颜色为 。 现在小阳有 种操作。 ：给 区间里所有贝壳的颜色值加上 。 ：询问 区间里所有相邻贝壳颜色值的差（取绝对值） 的最大值（若 输出 ）。 ：询问 区间里所有贝壳颜色值的最大公约数。 输入描述 展开全文
去ta的博客 赞 (9) 回复(2) 收起
头像 lifehappy
发表于 2020-12-21 18:43:47
小阳的贝壳 这里最难维护的应该是区间了，但是我们有一个结论，所以这一步可以转换为维护整个序列的差分。 对于操作一：我们只要对端点的值增加，对端点的值减小。 对于操作二：我们只要得到差分数组里的绝对值最大值就行了。 对于操作三：我们首先要得到，然后得到这一段差分序列的，然后再于求一个即为答案。 对一整 展开全文
去ta的博客 赞 (5) 回复(0) 收起
头像 Kur1su
发表于 2020-12-21 22:20:28
Description 链接：https://ac.nowcoder.com/acm/problem/26255来源：牛客网 小阳手中一共有 n 个贝壳，每个贝壳都有颜色，且初始第 i 个贝壳的颜色为 。现在小阳有 3 种操作： 1 l r x：给 [l,r]区间里所有贝壳的颜色值加上 x 。 2 展开全文
去ta的博客 赞 (5) 回复(0) 收起
头像 平凡的小白
发表于 2020-09-17 23:42:55
#include<bits/stdc++.h> #define js ios::sync_with_stdio(false);cin.tie(0);cout.tie(0) using namespace std; const int maxn=1e5+7; int a[maxn], 展开全文
去ta的博客 赞 (3) 回复(0) 收起
头像 埃兰希尔
发表于 2020-08-04 16:07:19
更好的阅读体验 简述概念和应用   所谓的差分，其实就是后一项与前一项的差，对于第一项而言， 。设数组 ，那么差分数组 ，即 ,那么， NC26255 小阳的贝壳  这题要求最大公因数和差分最值，最值上一题已经求过了，这最大公因数怎么维护出来呢？而且修改是区间修改的，这貌似也增加了 展开全文
去ta的博客 赞 (3) 回复(0) 收起
头像 issue是云哥的小迷×呀
发表于 2020-12-25 19:09:05
传送门 假设只有操作一和操作三 操作一普通线段树可以完成,操作三普通线段树也能完成 做法是维护一个数组表示节点表示区间的 由于具有传递性,所以很容易维护。 假如只有操作一和操作三 操作一普通线段树可以轻松完成,操作二的话....势必要维护一个差分数组 也就是令 在线段树上维护这个数组的关系 比如 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 pdd内推哈哈哈
发表于 2019-08-06 10:32:45
gcd查询 给定一个序列 有三种操作: :在区间 加上 . : 查询区间 中的 . :查询 . 根据 的性质, ,设 是 的差分数组,对于任意一个区间 由于 的性质,在区间 加上一个数其实只对 有用所以只需要维护 数组就可以单点更新即可,求询问2刚好 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 MYCui_
发表于 2020-12-21 22:06:12
前言 在错了N次之后，改动了一个小地方，多了一个+1就过了这一题，太惨了。 思路 假设只有前两个操作，我们实际上只需要生成一个差分数组，维护一个单点修改以及区间查询最大值即可。 但是最难的是操作3，区间GCD。 小蒟蒻在这里卡了许久，冥思苦想还是没有想到办法，最后百度：差分数组 与 区间GCD 然后 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 hnust_yangyanjun
发表于 2020-12-25 19:24:48
题意：有n个有颜色的贝壳，每一个的颜色值为col[i],小阳能进行以下三种操作：1 l r x：给 [l,r]区间里所有贝壳的颜色值加上x。 2 l r：询问 [l,r]区间里所有相邻贝壳颜色值的差（取绝对值）的最大值（若l=r输出0）。 3 l r ：询问 [l,r]区间里所有贝壳颜色值的最大公约 展开全文
去ta的博客 赞 (0) 回复(0) 收起
查看本题
查看本题讨论

相关比赛

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”