ABC238E Range Sums

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

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

题意

我们有一组长为 N 的数列 A，现在你知道 Q 组 $[L,R][L\; ,\; R]$ 并且知道 $A_L+\mathrm{.}\mathrm{.}\mathrm{.}+A_{R}A\_L+...+A\_R$ 的值。求解 $A_1+\mathrm{.}\mathrm{.}\mathrm{.}+A_{N}A\_1+...+A\_N$ 是否可知。

思路

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

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

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

code