Codeforces Round #176 (Div. 1 + Div. 2)

对于每个询问\(q\)来说，被墙的挡住的位置满足\(l_i\le x\le r_i,t_i\le q+x\)，即\(max\{l_i,t_i-q\}\le x \le r_i\)。
当\(l_i\)为最大值时,\(l_i\ge t_i - q\)，即\(q\ge t_i - li\)，考虑到\(q\)是严格递增的，所以可以按照\(t_i-l_i\)对墙排序，小于等于\(q\)的贡献为\(r_i-l_i\)。这个贡献与\(q\)无关，所以直接求和即可。
当\(t_i-q\)为最大值时，这些墙体的贡献为\(\sum{r_i-(t_i-q)}=\sum{r_i-t_i}+kq\)。所以需要维护\(r_i-ti\)的值以及相应的墙的数量。
由于墙会出现重叠情况，所以需要按照时间顺序，将墙处理成不相交的状态。离散化的方法是：用\(set\)维护未被覆盖的小区间，均摊复杂度为\(logn\)。

因为\(1\le a_i \le m\)，所以\(p_j=a_i\)，否则\(p_j\)无法用\(\sum{a_i}\)表示。
对于\(a_k\)来说，必然要存在\(a_k=a_i+a_j,k>i,j\)，否则会不满足条件2，剩下的就是用fft判断\(a_k=a_i+a_j\)这个等式是否成立。

巴特西