首页 > 牛牛的等差数列
开通博客写题解
头像 wxyww
发表于 2020-04-19 11:29:04
solution 用线段树维护即可。考虑线段树的懒标记如何维护。我们维护两个懒标记，添加到当前位置的数列在该区间开始位置的首项之和，表示这些添加的数列公差之和。 因为如果往一个位置添加了一个等差数列。其中某个位置可以看作，那么再添加一个等差数列，那么该位置就可以看作，相当于添加了一个首项为公差为的等 展开全文
去ta的博客 赞 (4) 回复(0) 收起
头像 18duangduang
发表于 2020-04-20 17:14:06
题面 #include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn=2e5+10; const int mod=3*5*7*11*13*17*19*23; const int i 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 ZevenWu
发表于 2020-04-18 15:21:45
solution：显然，<25的质数共有9个：2、3、5、7、11、13、17、19、23.它们的乘积的范围在2e9左右，设为d。一个显然的做法是对每一个质数维护答案。然后就是一个区间加等差数列区间求和，线段树即可。这样是O(9nlogn).也可以只维护一个%d的线段树，最后查询完在%即可。这 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 漂洋过海sail
发表于 2020-04-18 17:24:47
题意 一个数列，两个区间操作：加上一个等差数列；求和，对 取模。 算法（） 线段树应用，等差数列的处理要注意。会发现直接储存会爆 long long，而模数又不固定。观察 的范围，会发现 ，而 ，所以在操作过程中，可以直接对 取模。 代码 #include <cstdio> #inc 展开全文
去ta的博客 赞 (0) 回复(1) 收起
头像 精神病科黄主任
发表于 2020-05-04 17:53:59
经典线段树问题。我们知道等差数列加上等差数列还是一个等差数列。所以我们线段树维护区间的总和，当前位置的值，和公差即可。对于求区间和，因为模数是根据输入的，我们发现模数只到了25，所以我们考虑计算出来mod=lcm(1,2,3,....25)这样的mod一定时1到25中任意一个数的倍数。那么我们输出的 展开全文
去ta的博客 赞 (0) 回复(0) 收起
查看本题
查看本题讨论

相关比赛

等你来战

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

扫描二维码，进入QQ群

扫码关注“比赛自动姬”