2020-2021:teams:legal_string:组队训练比赛记录:contest4
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 | |||
|
2020-2021:teams:legal_string:组队训练比赛记录:contest4 [2021/07/22 10:53] jxm2001 [题解] |
2020-2021:teams:legal_string:组队训练比赛记录:contest4 [2021/07/25 00:00] (当前版本) jxm2001 [题解] |
||
|---|---|---|---|
| 行 17: | 行 17: | ||
| 于是问题转化为统计有多少区间满足 $\max(a[l\sim r])-\min(a[l\sim r])=(r-l)\text{gcd}(a_{l+1}-a_l\cdots a_r-a_{r-1})$。 | 于是问题转化为统计有多少区间满足 $\max(a[l\sim r])-\min(a[l\sim r])=(r-l)\text{gcd}(a_{l+1}-a_l\cdots a_r-a_{r-1})$。 | ||
| - | 考虑构造序列 $b_i=\max(a[i\sim r])-\min(a[i\sim r])+l\times \text{gcd}(a_{i+1}-a_i\cdots a_r-a_{r-1})$。 | + | 考虑构造序列 $b_i=\max(a[i\sim r])-\min(a[i\sim r])+i\times \text{gcd}(a_{i+1}-a_i\cdots a_r-a_{r-1})$。 |
| 线段树维护区间最小值和最小值个数，对固定的 $r$，统计 $[i,r](i\lt r)$ 贡献时，枚举 $\text{gcd}(a_{i+1}-a_i\cdots a_r-a_{r-1})$ 不同的区间。 | 线段树维护区间最小值和最小值个数，对固定的 $r$，统计 $[i,r](i\lt r)$ 贡献时，枚举 $\text{gcd}(a_{i+1}-a_i\cdots a_r-a_{r-1})$ 不同的区间。 | ||
2020-2021/teams/legal_string/组队训练比赛记录/contest4.1626922388.txt.gz · 最后更改: 2021/07/22 10:53 由 jxm2001
