Range Sums

 

https://atcoder.jp/contests/abc238/tasks/abc238_e

这个题目属实没想到,头一次在这个颜色的题目上栽跟头了。

不过也算上一种开开眼界了吧。

题意

我们有一组长为 N 的数列 A,现在你知道 Q 组 $[L , R]$ 并且知道 $A_L+…+A_R$ 的值。求解 $A_1+…+A_N$ 是否可知。

思路

我们可以将数列 $A$ 转化为前缀 $S$ 那么对于每次知道的的 $[L , R]$ 就可以相应的转化为 $S_R - S_{L - 1}$ 。

那么每次我们都得到一组 $(L - 1 , R)$ 如果我们将这个模型转化为图的的话,我们最终的目标是 $S_N - S_0$ 那么也就变成了存在一条从点 $0$ 通往点 $N$ 的一条路径。

那么的话,我们可以通过dfs的形式获得答案,也可以通过并查集等等等形式。

code

algorithm